control 掌控方法记录( 二 ) _生活百科

文章插图
为了提高效率，我们选择边建树边倍增，建树复杂度\(nlogn\) 。
void cone(int a,int b)//cone=conect{ f[a][0]=b; dep[a]=dep[b]+1; add(b,a); for(int i=1;f[f[a][i-1]][i-1];i++) {f[a][i]=f[f[a][i-1]][i-1]; }}int get_lca(int x,int y)//倍增lca{ if(dep[x]<dep[y]) swap(x,y); for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y) return x; for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0];}再考虑回答询问。
【control 掌控方法记录】根据我们建树时遵循的求LCA的原则，发现每个询问就是求给出所有点到根的并集的节点数。考虑将所有节点按\(dfn\)排序，则将每个节点与其相邻的节点的LCA加起来就是答案。

文章插图
void dfs(int now)//求dfn{ dfn[now]=++cnt; for(int i=head[now];i;i=E[i].nex) dfs(E[i].v);}for(int i=1,t;i<=q;i++) {re(t);for(int j=1;j<=t;j++) re(meet[j]);sort(meet+1,meet+t+1,cmp);//按dfn排序int ans=dep[meet[1]];for(int j=2;j<=t;j++) ans+=dep[meet[j]]-dep[get_lca(meet[j],meet[j-1])];printf("%d\n",ans); }完整AC代码
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=200005;template <typename T>inline void re(T &x) { x=0; int f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-f; for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48); x*=f; return;}int n,q;int head[N],totr;struct edge{ int u,v,nex;}E[N<<1];void add(int u,int v){ E[totr++].u=u; E[totr].v=v; E[totr].nex=head[u]; head[u]=totr;}int f[N][20],dfn[N],meet[N],dep[N];void cone(int a,int b)//cone=conect{ f[a][0]=b; dep[a]=dep[b]+1; add(b,a); for(int i=1;f[f[a][i-1]][i-1];i++) {f[a][i]=f[f[a][i-1]][i-1]; }}int get_lca(int x,int y)//倍增lca{ if(dep[x]<dep[y]) swap(x,y); for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y) return x; for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0];}int cnt;void dfs(int now)//求dfn{ dfn[now]=++cnt; for(int i=head[now];i;i=E[i].nex) dfs(E[i].v);}bool cmp(int a,int b){ return dfn[a]<dfn[b];}int main(){ freopen("control.in","r",stdin); freopen("control.out","w",stdout); re(n); for(int i=1,k;i<=n;i++) {re(k);int lca=0;if(k) re(lca);for(int j=1,mana;j<k;j++){re(mana);lca=get_lca(lca,mana);}cone(i,lca); } re(q); dfs(0); for(int i=1,t;i<=q;i++) {re(t);for(int j=1;j<=t;j++) re(meet[j]);sort(meet+1,meet+t+1,cmp);//按dfn排序int ans=dep[meet[1]];for(int j=2;j<=t;j++) ans+=dep[meet[j]]-dep[get_lca(meet[j],meet[j-1])];printf("%d\n",ans); } return 0;}参考

control 掌控方法记录( 二 )

推荐阅读

身体突然长胖是因为缺乏什么因素吗？

2022呼和浩特疫情期间地铁进站乘车最新要求

哈弗m6车身颜色有几种哈弗M6有哪几种颜色

裤子掉档是什么意思啊裤子掉档的怎么处理

分享29个营销理论什么是色彩营销？

蛋白质粉里含雌激素吗？蛋白质粉中会含有雌激素吗

黑衣人迅雷黑衣人迅雷mp4下载

吉利博越m挡什么时候用吉利博越M挡有什么用

一带一路什么意思一带一路是指什么

孩子有了个假想中的朋友，家长速度反思是否平时忽略了孩子？

分享华为手机换电池步骤华为智能手机怎么换电池教程

灵芝红枣水的功效灵芝红枣水的正确煮法

亚历山大大帝东征最远到达了哪里

传奇三新手必看攻略传奇3地图新手怎么样玩

南京有红宝石蛋糕店吗，红宝石蛋糕店

有没有哪些相亲渠道免费且靠谱？

迢迢牵牛星中脉脉的意思

这些生肖最喜欢送对方定情信物？

常见的美系车品牌有哪些美国汽车品牌排行榜前十名

女人排毒吃什么最好女生吃什么排毒

control 掌控 方法记录( 二 )

推荐阅读

control 掌控方法记录( 二 )