虚树入门！世界树！
虚树，顾名思义，就是建一颗虚假的树
（其实这道题不适合用来入门，树形dp的部分比较难）
这个树和原树的区别就是，他只保留了一些询问的必要节点，和必要节点之间的lca。这样能让这颗虚树具有树的性质，且不改变点之间的相对位置。
然后这颗虚树的节点数最多只有询问点数*2个，这样可以大幅度降低单词询问的复杂度。然后通过树形dp来解决问题。
题目来源：BZOJ3572
世界树啊 这个题我感觉很麻烦 难点不在虚树，而是树形dp啊
我大概说一下做法吧
1、手动把1这个节点加入虚树中，成为虚树的根（判断一下询问点有没有1）。（因为这题需要用到深度啊，子树大小啊之类的，所以根经常变的话会很难做）
2、树形dp吧，对于虚树上每个非询问点，找到一个和他自己最近的节点。（这里注意一下。。我是求错了几次。。找了半天）。。
3、然后对虚树上相邻的两个节点之间的边进行二分，找到距离的分界点。
4、把每个节点的贡献加到离自己最近的节点上。（注意有一些没有统计到的节点也要统计进去）（具体是用子树大小减减减）
代码如下：
1 #include<stdio.h> 2 #include<string.h> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 ///////////--虚树模板--/////////////////// 7 //传入树的一个子集，若以按dfs序排好直接调用build_vtree 8 //否则调用vsort 9 //复杂度O( nlog(n) ) n是虚树的大小 10 11 #define N 330000 12 #define LN 21 13 14 ////////////--标准建邻接表--///////////// 15 struct node 16 { 17 int to,next; 18 } edge[2*N]; 19 20 int cnt,pre[N]; 21 22 void creat() 23 { 24 memset(pre,-1,sizeof(pre)); 25 cnt=0; 26 } 27 28 void add_edge(int u,int v) 29 { 30 edge[cnt].to = v; 31 edge[cnt].next = pre[u]; 32 pre[u] = cnt++; 33 } 34 ////////////////////////////////////// 35 36 int deep[N];//记录每个点的深度 37 int order[N];//记录每个点的访问次序 38 int sz[N]; 39 int indx=0; 40 41 struct Lca_Online 42 { 43 int _n; 44 45 int dp[N][LN]; 46 47 void _dfs(int s,int fa,int dd) 48 { 49 sz[s]=1; 50 deep[s] = dd; 51 order[s] = ++indx; 52 for(int p=pre[s]; p!=-1; p=edge[p].next) 53 { 54 int v = edge[p].to; 55 if(v == fa) 56 continue; 57 _dfs(v,s,dd+1); 58 sz[s]+=sz[v]; 59 dp[v][0] = s; 60 } 61 } 62 63 void _init() 64 { 65 for(int j=1; (1<<j)<=_n; j++) 66 { 67 for(int i=1; i<=_n; i++) 68 { 69 if(dp[i][j-1]!=-1) 70 dp[i][j] = dp[ dp[i][j-1] ][j-1]; 71 } 72 } 73 } 74 void lca_init(int n) 75 { 76 _n = n; 77 memset(dp,-1,sizeof(dp)); 78 //_dfs(firstid,-1,0); 79 indx = 0; 80 _dfs(1,-1,0); 81 _init(); 82 } 83 84 int lca_query(int a,int b) 85 { 86 if(deep[a]>deep[b]) 87 swap(a,b); 88 //调整b到a的同一高度 89 for(int i=LN-1; deep[b]>deep[a]; i--) 90 if(deep[b]-(1<<i) >= deep[a]) 91 b = dp[b][i]; 92 if(a == b) 93 return a; 94 for(int i=LN-1; i>=0; i--) 95 { 96 if(dp[a][i]!=dp[b][i]) 97 a = dp[a][i],b = dp[b][i]; 98 } 99 return dp[a][0]; 100 } 101 } lca; 102 103 int stk[N],top; 104 int mark[N];//标示虚树上的点是否是无用点 105 vector<int>tree[N];//存边 106 vector<int>treew[N];//存权 107 108 void tree_add(int u,int v,int w) 109 { 110 tree[u].push_back(v); 111 tree[v].push_back(u); 112 treew[u].push_back(w); 113 treew[v].push_back(w); 114 } 115 int dis(int a,int b) 116 { 117 return deep[a]+deep[b]-2*deep[lca.lca_query(a,b)]; 118 } 119 120 int belong[N],h[N],ans[N],c[N],f[N]; 121 122 void fz(int fa,int s) 123 { 124 int x=s,low=s; 125 for(int i=20; i>=0; i--) 126 if(lca.dp[low][i]!=-1) 127 if(deep[lca.dp[low][i]]>deep[fa]) 128 low=lca.dp[low][i]; 129 c[fa]-=sz[low]; 130 if(belong[fa]==belong[s]) 131 { 132 f[belong[fa]]+=sz[low]-sz[s]; 133 return ; 134 } 135 x=s; 136 for(int i=20; i>=0; i--) 137 if(lca.dp[x][i]!=-1&&deep[lca.dp[x][i]]>=deep[low]) 138 if(dis(belong[fa],lca.dp[x][i])>dis(lca.dp[x][i],belong[s])) 139 x=lca.dp[x][i]; 140 if(belong[s]<belong[fa]&&dis(belong[fa],lca.dp[x][0])==dis(belong[s],lca.dp[x][0])&&lca.dp[x][0]!=fa) 141 { 142 x=lca.dp[x][0]; 143 f[belong[fa]]+=sz[low]-sz[x]; 144 f[belong[s]]+=sz[x]-sz[s]; 145 } 146 else 147 { 148 f[belong[fa]]+=sz[low]-sz[x]; 149 f[belong[s]]+=sz[x]-sz[s]; 150 } 151 } 152 153 void dfs2(int now,int fa) 154 { 155 c[now]=f[now]=belong[now]=mark[now]=ans[now]=0; 156 for(int i=0; i<tree[now].size(); i++) 157 { 158 if(tree[now][i]==fa) 159 continue; 160 dfs2(tree[now][i],now); 161 } 162 tree[now].clear(); 163 treew[now].clear(); 164 } 165 void dfs1(int now,int fa) 166 { 167 c[now]=sz[now]; 168 for(int i=0; i<tree[now].size(); i++) 169 { 170 if(tree[now][i]==fa) 171 continue; 172 dfs1(tree[now][i],now); 173 if(mark[now]==0) 174 { 175 int t=belong[tree[now][i]]; 176 int t1=dis(now,t),t2=dis(now,belong[now]); 177 if(!belong[now]||t1<t2||t1==t2&&t<belong[now]) 178 belong[now]=t; 179 } 180 } 181 } 182 void dfs3(int now,int fa) 183 { 184 if(fa!=0&&mark[now]==0) 185 { 186 int t=belong[fa]; 187 int t1=dis(t,now),t2=dis(now,belong[now]); 188 if(!belong[now]||t1<t2||t1==t2&&t<belong[now]) 189 belong[now]=t; 190 } 191 for(int i=0; i<tree[now].size(); i++) 192 if(tree[now][i]!=fa) 193 { 194 dfs3(tree[now][i],now); 195 196 } 197 } 198 void dfss(int now,int fa) 199 { 200 for(int i=0; i<tree[now].size(); i++) 201 if(tree[now][i]!=fa) 202 {fz(now,tree[now][i]); 203 dfss(tree[now][i],now); 204 205 } 206 } 207 void dfsss(int now,int fa) 208 { 209 for(int i=0; i<tree[now].size(); i++) 210 if(tree[now][i]!=fa) 211 dfsss(tree[now][i],now); 212 ans[belong[now]]+=c[now]+f[now]; 213 } 214 215 //使用前调用 lca.lca_init(n); 初始化 216 //返回虚树根节点,虚树的边默认为原树上两点的距离 217 int build_vtree(int vp[],int vn)//传入按dfs序数组，以及长度(要自己写按dfs排序的数组) 218 { 219 if(vn == 0) 220 return -1; 221 top = 0; 222 for(int i=0; i<vn; i++) 223 belong[vp[i]]=vp[i]; 224 int i=0; 225 if(belong[1]==1) 226 { 227 stk[top++] = vp[0]; 228 tree[ vp[0] ].clear(); 229 treew[ vp[0] ].clear(); 230 mark[ vp[0] ]=1; 231 i++; 232 } 233 else 234 { 235 stk[top++] = 1; 236 tree[1].clear(); 237 treew[1].clear(); 238 } 239 for(; i<vn; i++) 240 { 241 int v = vp[i]; 242 243 int plca = lca.lca_query(stk[top-1], v);//最近公共祖先 244 if(plca == stk[top-1]) ;//不处理 245 else 246 { 247 int pos=top-1; 248 while(pos>=0 && deep[ stk[pos] ]>deep[plca]) 249 pos--; 250 pos++; 251 for(int j=pos; j<top-1; j++) 252 { 253 tree_add(stk[j],stk[j+1],deep[stk[j+1]]-deep[stk[j]]); 254 } 255 int prepos = stk[pos]; 256 if(pos == 0) 257 { 258 tree[plca].clear(),treew[plca].clear(),stk[0]=plca,top=1; 259 mark[plca] = 0; 260 } 261 else if(stk[pos-1] != plca) 262 { 263 tree[plca].clear(),treew[plca].clear(),stk[pos]=plca,top=pos+1; 264 mark[plca] = 0; 265 } 266 else 267 top = pos; 268 tree_add(prepos,plca,deep[prepos]-deep[plca]); 269 270 } 271 tree[v].clear(); 272 treew[v].clear(); 273 stk[top++] = v; 274 mark[v] = 1; 275 } 276 for(i=0; i<top-1; i++) 277 { 278 tree_add(stk[i], stk[i+1], deep[stk[i+1]]-deep[stk[i]]); 279 } 280 dfs1(1,0); 281 dfs3(1,0); 282 dfss(1,0); 283 dfsss(1,0); 284 return 1; 285 } 286 287 //////////////--先排序，再建虚树--////////////////////// 288 struct vnode 289 { 290 int order,id; 291 } vg[N]; 292 int vcmp(vnode t1,vnode t2) 293 { 294 return t1.order<t2.order; 295 } 296 int b[N]; 297 int vsort(int vp[],int vn)//传入未排序的数组，以及长度. 298 { 299 for(int i=0; i<vn; i++) 300 b[i]=vg[i].id = vp[i],vg[i].order = order[ vp[i] ]; 301 sort(vg,vg+vn,vcmp); 302 for(int i=0; i<vn; i++) 303 vp[i]=vg[i].id; 304 build_vtree(vp, vn); 305 for(int i=0; i<vn; i++) 306 printf("%d ",ans[b[i]]); 307 puts(""); 308 dfs2(1,0); 309 return 1; 310 } 311 int main() 312 { 313 int n; 314 scanf("%d",&n); 315 creat(); 316 for(int i=1,x,y; i<n; i++) 317 { 318 scanf("%d%d",&x,&y); 319 add_edge(x,y); 320 add_edge(y,x); 321 } 322 int Q; 323 scanf("%d",&Q); 324 lca.lca_init(n); 325 for(int q=1; q<=Q; q++) 326 { 327 int m; 328 scanf("%d",&m); 329 for(int i=0; i<m; i++) 330 scanf("%d",h+i); 331 vsort(h,m); 332 } 333 }
View Code
版权声明：本文为xseventh原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。