题目大意：给出一棵n个结点的树，每条边的长度为1。q个询问，每个询问中选出m个点，所有点会从选出的点中挑一个最近的且编号尽量小的点被其管理，求每一个选出的点管理多少点
每次询问在树上选择一些点的问题可以用虚树解决，能够减少扫描无用的点浪费的时间
对于虚树上的点DP一下求出与这个点最近的被选出的点(记这样的点为near点)。虚树上的每一条边省略了一些在原树上的点，这些点一定是被 边的两个端点的near点 管理。对于虚树的每一条边在原树上倍增找到从哪里断开更新答案即可。
#include <cstdio> #include <cstring> #include <algorithm> #define N 300005 using namespace std; int tot=-1,fir[N]; struct Edge { int from,to,nxt; Edge() {} Edge(int _from,int _to):from(_from),to(_to),nxt(fir[_from]) {} }e[N*2]; void Add_Edge(int from,int to) { if(from==to) return ; e[++tot]=Edge(from,to); fir[from]=tot; return ; } int n,m,T,dfs_clock,pa[N][20],dpt[N],siz[N],pos[N]; void dfs(int x) { pos[x]=++dfs_clock; dpt[x]=dpt[pa[x][0]]+1; siz[x]=1; for(int i=fir[x];~i;i=e[i].nxt) { if(e[i].to==pa[x][0]) continue; pa[e[i].to][0]=x; dfs(e[i].to); siz[x]+=siz[e[i].to]; } return ; } int LCA(int x,int y) { if(dpt[x]<dpt[y]) swap(x,y); for(int i=18;~i;i--) if(dpt[pa[x][i]]>=dpt[y]) x=pa[x][i]; if(x==y) return x; for(int i=18;~i;i--) if(pa[x][i]!=pa[y][i]) x=pa[x][i], y=pa[y][i]; return pa[x][0]; } int dist(int x,int y) { return dpt[x]+dpt[y]-2*dpt[LCA(x,y)]; } int top,query[N],q[N],s[N],near[N],seq[N],sum[N],ans[N]; bool cmp(const int& lhs,const int& rhs) { return pos[lhs]<pos[rhs]; } void find_near1(int x) { seq[++dfs_clock]=x; sum[x]=siz[x]; for(int i=fir[x];~i;i=e[i].nxt) { find_near1(e[i].to); int now_dist=dist(near[x],x),new_dist=dist(x,near[e[i].to]); if(now_dist>new_dist || now_dist==new_dist && near[e[i].to]<near[x] || !near[x]) near[x]=near[e[i].to]; } return ; } void find_near2(int x) { for(int i=fir[x];~i;i=e[i].nxt) { int now_dist=dist(near[e[i].to],e[i].to),new_dist=dist(near[x],e[i].to); if(now_dist>new_dist || now_dist==new_dist && near[e[i].to]>near[x]) near[e[i].to]=near[x]; find_near2(e[i].to); } return ; } void calc(int x,int y) { int z=y,mid=y; for(int i=18;~i;i--) if(dpt[pa[z][i]]>dpt[x]) z=pa[z][i]; sum[x]-=siz[z]; if(near[x]==near[y]) { ans[near[x]]+=siz[z]-siz[y]; return ; } for(int i=18;~i;i--) { int to=pa[mid][i]; if(dpt[to]<=dpt[x]) continue; int dist_x=dist(near[x],to),dist_y=dist(near[y],to); if(dist_x>dist_y || dist_x==dist_y && near[y]<near[x]) mid=to; } ans[near[x]]+=siz[z]-siz[mid]; ans[near[y]]+=siz[mid]-siz[y]; return ; } int main() { //input memset(fir,-1,sizeof fir); scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); Add_Edge(x,y), Add_Edge(y,x); } //initialize dfs(1); for(int i=1;i<=18;i++) for(int x=1;x<=n;x++) pa[x][i]=pa[pa[x][i-1]][i-1]; //query memset(fir,-1,sizeof fir); for(scanf("%d",&T);T;T--) { scanf("%d",&m); top=dfs_clock=0; tot=-1; for(int i=1;i<=m;i++) scanf("%d",query+i), q[i]=query[i], near[q[i]]=q[i]; //build tree sort(q+1,q+m+1,cmp); s[++top]=1; for(int i=1;i<=m;i++) { int lca=LCA(s[top],q[i]); while(dpt[lca]<dpt[s[top-1]]) Add_Edge(s[top-1],s[top]), top--; Add_Edge(lca,s[top--]); if(s[top]!=lca) s[++top]=lca; if(s[top]!=q[i]) s[++top]=q[i]; } while(--top) Add_Edge(s[top],s[top+1]); //DP find_near1(1), find_near2(1); //calculate answer for(int i=1;i<=dfs_clock;i++) for(int j=fir[seq[i]];~j;j=e[j].nxt) calc(seq[i],e[j].to); for(int i=1;i<=dfs_clock;i++) ans[near[seq[i]]]+=sum[seq[i]]; //output for(int i=1;i<=m;i++) printf("%d ",ans[query[i]]); printf("\n"); //set array for(int i=1;i<=dfs_clock;i++) ans[seq[i]]=sum[seq[i]]=near[seq[i]]=0, fir[seq[i]]=-1; } return 0; }