题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3572
算是细节题了吧。。
构出虚树，考虑z正反DP两次求出虚树中每个点最近的议事处是哪一个点，然后枚举虚树中的每一条边${X->Y}$，对于两点间在原树中的路径，显然存在一个分界点使得自分界点之上的所有点归最靠近$X$的议事处管辖，之下的点归最靠经$Y$的议事处管辖，还有一些没有考虑过的点，另外统计一下即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 310000 10 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,f[maxn][22],deep[maxn],dfn[maxn],cnt,size[maxn],s[maxn],top; 13 llg a[maxn],b[maxn],bel[maxn],c[maxn],rem[maxn],ans[maxn]; 14 15 vector<llg>g[maxn]; 16 17 bool cmp(llg x,llg y) {return dfn[x]<dfn[y];} 18 19 void link(llg x,llg y){g[x].push_back(y);} 20 21 void dfs(llg x,llg fa) 22 { 23 dfn[x]=++cnt; 24 llg w=g[x].size(),v; 25 size[x]=1; 26 for (llg i=0;i<w;i++) 27 { 28 v=g[x][i]; 29 if (v==fa) continue; 30 deep[v]=deep[x]+1; 31 f[v][0]=x; 32 dfs(v,x); 33 size[x]+=size[v]; 34 } 35 } 36 37 void make_f() 38 { 39 for (llg j=1;j<=20;j++) 40 for (llg i=1;i<=n;i++) 41 f[i][j]=f[f[i][j-1]][j-1]; 42 } 43 44 llg lca(llg x,llg y) 45 { 46 if (deep[x]<deep[y]) swap(x,y); 47 for (llg i=20;i>=0;i--) 48 if (deep[f[x][i]]>=deep[y]) 49 x=f[x][i]; 50 if (x==y) return x; 51 for (llg i=20;i>=0;i--) 52 if (f[x][i]!=f[y][i]) 53 { 54 x=f[x][i]; 55 y=f[y][i]; 56 } 57 return f[x][0]; 58 } 59 60 llg dis(llg x,llg y) {return deep[x]+deep[y]-2*deep[lca(x,y)];} 61 62 void init() 63 { 64 cin>>n; 65 llg x,y; 66 for (llg i=1;i<n;i++) 67 { 68 scanf("%lld%lld",&x,&y); 69 g[x].push_back(y),g[y].push_back(x); 70 } 71 deep[1]=1; 72 dfs(1,-1); 73 make_f(); 74 } 75 76 void build_tree() 77 { 78 cnt=top=0; 79 sort(a+1,a+m+1,cmp); 80 if (bel[1]!=1) s[++top]=1; 81 for (llg i=1;i<=m;i++) 82 { 83 llg x=a[i],fa=0; 84 while (top) 85 { 86 fa=lca(s[top],x); 87 if (top>1 && deep[fa]<deep[s[top-1]]) 88 { 89 link(s[top-1],s[top]); 90 top--; 91 } 92 else 93 if (deep[fa]<deep[s[top]]){ link(fa,s[top--]); break;} 94 else 95 break; 96 97 } 98 if (s[top]!=fa) s[++top]=fa; 99 s[++top]=x; 100 } 101 while (--top) link(s[top],s[top+1]); 102 } 103 104 void dfs1(llg x,llg fa) 105 { 106 c[++cnt]=x; 107 rem[x]=size[x]; 108 llg w=g[x].size(),v; 109 for (llg i=0;i<w;i++) 110 { 111 v=g[x][i]; 112 dfs1(v,x); 113 if (v==fa) continue; 114 if (!bel[v]) continue;//why 115 llg d1=dis(bel[v],x),d2=dis(bel[x],x); 116 if ((d1==d2 && bel[v]<bel[x]) || (d1<d2) || !bel[x]) bel[x]=bel[v]; 117 } 118 } 119 120 void dfs2(llg x,llg fa) 121 { 122 llg w=g[x].size(),v; 123 for (llg i=0;i<w;i++) 124 { 125 v=g[x][i]; 126 if (v==fa) continue; 127 llg d1=dis(bel[x],v),d2=dis(bel[v],v); 128 if ((d1==d2 && bel[v]>bel[x]) || (d1<d2) || !bel[v]) 129 bel[v]=bel[x]; 130 dfs2(v,x); 131 } 132 } 133 134 void work(llg x,llg y) 135 { 136 llg son=y,mid=y; 137 for (llg i=20;i>=0;i--) 138 if (deep[f[son][i]]>deep[x]) son=f[son][i]; 139 rem[x]-=size[son]; 140 if (bel[x]==bel[y]) {ans[bel[x]]+=size[son]-size[y]; return;} 141 for (llg i=20;i>=0;i--) 142 { 143 llg ne=f[mid][i]; 144 if (deep[ne]<=deep[x]) continue; 145 llg d1=dis(bel[x],ne),d2=dis(bel[y],ne); 146 if (d1>d2 || (d1==d2 && bel[y]<bel[x])) mid=ne; 147 } 148 ans[bel[x]]+=size[son]-size[mid]; 149 ans[bel[y]]+=size[mid]-size[y]; 150 } 151 152 int main() 153 { 154 yyj("tree"); 155 init(); 156 llg T; cin>>T; 157 for (llg i=1;i<=n;i++) 158 { 159 while (!g[i].empty()) g[i].pop_back(); 160 //std::vector(c).swap(vec); 161 } 162 while (T--) 163 { 164 scanf("%lld",&m); 165 for (llg i=1;i<=m;i++) 166 { 167 scanf("%lld",&a[i]); 168 b[i]=a[i]; bel[a[i]]=a[i]; 169 } 170 build_tree(); 171 dfs1(1,-1); dfs2(1,-1); 172 for (llg i=1;i<=cnt;i++) 173 { 174 llg w=g[c[i]].size(); 175 llg la=-1; 176 for (llg j=0;j<w;j++) 177 { 178 if (g[c[i]][j]==la) continue; 179 la=g[c[i]][j]; 180 work(c[i],g[c[i]][j]); 181 } 182 } 183 for (llg i=1;i<=cnt;i++) ans[bel[c[i]]]+=rem[c[i]]; 184 for (llg i=1;i<=m;i++) printf("%lld ",ans[b[i]]); 185 printf(" "); 186 for (llg i=1;i<=cnt;i++) 187 { 188 ans[c[i]]=bel[c[i]]=rem[c[i]]=0; 189 while (!g[c[i]].empty()) g[c[i]].pop_back(); 190 } 191 } 192 return 0; 193 }