题目链接:世界树

  首先看到\(\sum m_i\le 3\times 10^5\)这个条件,显然这道题就需要用虚树了。

  在我们构建出虚树之后,就可以用两遍\(dfs\)来求出离每个点最近的议事处了。然后,如果一个点和它在虚树上的父亲所属的议事处不同,那么在原树中的两点之间的路径上就会存在一个分界点,倍增出这个分界点算答案即可。注意不能用路径长度来算,需要使用子树大小。

  然后我们还需要考虑那些不在虚树中的点。我们可以令\(f_x\)表示原树上\(x\)子树中和\(x\)属于同一个议事处的点的个数,那么我们可以把初值赋为\(size_x\),然后减去和它不属于同一个议事处的孩子的\(size\)和这条路径上点的个数即可。然后就可以直接用这个东西和上一部分的贡献一起算出答案了。

  想清楚了细节再写的话还是不难写的。

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 300010 using namespace std;
typedef long long llg; int head[maxn],next[maxn<<1],to[maxn<<1],tt;
int fa[maxn][19],dep[maxn],n,m,le[maxn],siz[maxn];
int d[maxn],ld,S[maxn],top,qu[maxn],nu[maxn],lq;
int fr[maxn],fd[maxn],ans[maxn],ji[maxn]; int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
} bool cmp(int x,int y){return le[x]<le[y];}
void link(int x,int y){
to[++tt]=y;next[tt]=head[x];head[x]=tt;
to[++tt]=x;next[tt]=head[y];head[y]=tt;
} void dfs(int u,int ff){
fa[u][0]=ff; dep[u]=dep[ff]+1; le[u]=++tt; siz[u]=1;
for(int i=1,now=2;now<dep[u];i++,now<<=1)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u],v;v=to[i],i;i=next[i])
if(v!=ff) dfs(v,u),siz[u]+=siz[v];
} int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y); int t=1;
for(int now=2;now<dep[x];now<<=1) t++;t--;
for(int i=t;i>=0;i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return x;
for(int i=t;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
} bool pd(int a,int b,int c,int d){return (a<b || (a==b && fr[c]<fr[d]));}
int dis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
int jump(int x,int y){
for(int i=18;i>=0;i--)
if(dep[fa[x][i]]>dep[y]) x=fa[x][i];
return x;
} void solve(int x,int y,int l){
int x1=fd[x],x2=fd[y]+dep[x]-dep[y],u=x;
for(int i=18,v,j=1<<18;i>=0;i--,j>>=1){
v=fa[u][i]; if(dep[v]<=dep[y]) continue;
if(pd(x1+j,x2-j,x,y)) x1+=j,x2-=j,u=fa[u][i];
}
ans[nu[fr[x]]]+=siz[u]-siz[x];
ans[nu[fr[y]]]+=siz[l]-siz[u];
} void dfs1(int u,int ff){
for(int i=head[u],v,x;v=to[i],i;i=next[i])
if(v!=ff){
dfs1(v,u);
if(fr[v] && fd[u]){
x=dis(u,fr[v]);
if(pd(x,fd[u],v,u)) fd[u]=x,fr[u]=fr[v];
}
}
} void dfs2(int u,int ff){
int x; ji[u]=siz[u];
if(ff && fr[ff]!=fr[u]){
x=dis(fr[ff],u);
if(pd(x,fd[u],ff,u)) fd[u]=x,fr[u]=fr[ff];
}
for(int i=head[u],v;v=to[i],i;i=next[i])
if(v!=ff){
dfs2(v,u); x=jump(v,u);
if(fr[v]!=fr[u]) ji[u]-=siz[v]+siz[x]-siz[v];
else ans[nu[fr[u]]]-=ji[v],ji[u]-=siz[v]-ji[v];
}
x=jump(u,ff); ans[nu[fr[u]]]+=ji[u];
if(ff && fr[u]!=fr[ff] && ff!=fa[u][0]) solve(u,ff,x);
} int main(){
File("worldtree");
n=getint();
for(int i=2;i<=n;i++) link(getint(),getint());
tt=0; dfs(1,0); tt=0; m=getint();
for(int i=1;i<=n;i++) head[i]=0,fd[i]=n+1;
while(m--){
lq=getint(); tt=0; d[ld=1]=1;
for(int i=1;i<=lq;i++){
nu[qu[i]=getint()]=i;
fr[qu[i]]=qu[i],fd[qu[i]]=0;
}
sort(qu+1,qu+lq+1,cmp); S[top=1]=1;
for(int i=1,L,x;i<=lq;i++){
x=qu[i]; L=lca(x,S[top]);
while(top){
if(top>1 && dep[S[top-1]]>dep[L]) link(S[top-1],S[top]),top--;
else if(dep[S[top]]>dep[L]){link(L,S[top--]);break;}
else break;
}
if(S[top]!=L) S[++top]=L,d[++ld]=L;
if(x!=1) S[++top]=x,d[++ld]=x;
}
while(top>1) link(S[top-1],S[top]),top--;
dfs1(1,0); dfs2(1,0);
for(int i=1,u;u=d[i],i<=ld;i++) head[u]=fr[u]=0,fd[u]=n+1;
for(int i=1;i<=lq;i++) printf("%d ",ans[i]);
for(int i=1;i<=lq;i++) ans[i]=0;
printf("\n");
}
return 0;
}

最新文章

  1. javaweb优化
  2. Python学习笔记——迭代器(RandSeq和AnyIter)
  3. mysql常见命令
  4. jax-rs中的一些参数标注简介(@PathParam,@QueryParam,@MatrixParam,@HeaderParam,@FormParam,@CookieParam)
  5. golang 自定义封包协议(转的)
  6. 解决ssh登录后闲置时间过长而断开连接
  7. css盒子模型 padding
  8. 进程控制之system函数
  9. 【转】@Override must override a superclass method 问题解决
  10. hdu 2126
  11. 开源代码搜索器searchcode
  12. iOS之短信认证
  13. 深入浅出Node.js (1) - Node简介
  14. SourceTree 将本地已有的git项目推送到远程git仓库
  15. 自理一遍android 高级知识
  16. 打印机驱动冲突和端口异常:win10更新部分补丁后,打印机本地连接(连接打印机的主机)可以打印,其他共享网络中的电脑可以连接到打印机,但不能打印——解决方案
  17. Xcode 中的断言
  18. Android device debug (adb) by Charge Only mode
  19. 设置radio选中
  20. #4 Python面向对象(三)

热门文章

  1. 【BZOJ2118】墨墨的等式 最短路
  2. Android EditText光标颜色 与inputType
  3. 【node】------mongoose的基本使用------【巷子】
  4. 160225、解决纯js文件国际化的问题
  5. yii2GridView的简单使用
  6. opencv学习笔记——minMaxIdx函数的含义及用法
  7. kitkat-s5p4418drone 记录
  8. H5上传压缩图片
  9. 如何编写一个python项目
  10. 不登录到MySQL执行SQL语句