题解 P4103 【[HEOI2014]大工程 】

不知到大家知不知道一个姿势叫“虚树” ### 虚树的构建 _（这里的构建虚树法较之网上的更为简单粗暴，如果想看优雅一点的，自行百度好了）_ 先说啥叫虚树，虚树，并不是不存在的树，相反，他是一个大树的一部分，凭借一个虚树，我们可以得知整体的部分信息。如果类比于序列，虚树和大树相当于，子序列和序列，而子树和大树相当于子区间和区间。 好了还是讲这道题吧，我们发现一个有趣的事实sigma k是O(n)的 如果对于每一次询问做一个树形dp，复杂度过高而无法承受，所以我们要想一个办法，把每一次树形dp的复杂度降到O(k)级别，这样总复杂度降至O(n) 也就是说，我们要从原来的树上“抽取”一只树，在这个树上面跑树形dp。 然后这里就有一个虚树的构建方法了，我们把询问点按照大树上的dfs序排序 ，之后每个相邻点求一遍lca，对于这些lca和询问点构成的点集，如果我们把树上路径看作边，路径长度看作边权，那么这些点事实上构成了一棵树，而且我们发现这个树上还可以跑树形dp，而对于这道题，维护的信息在带权树上都是可以实现的。 下面是dp做法， 我们设sum\[i]表示以i为根的子树中所有询问点到i的路径长度之和 设siz\[i]表示以i为根的子树中询问点的个数。 min\[i]表示以i为根的子树中询问点到i的最短路径 max\[i]表示以i为根的子树中询问点到i的最长路径 那么我们发现这个是可以向上递推的，我们在这只**虚树上dfs**，遍历点u的所有出边的时候，我们要考虑u的所有儿子形成的类似于v1-u-v2的路径，换言之，我们dp出来的是树上路径的一半，然后通过dfs枚举lca把dp出来的路径接起来 先说min和max吧 我们发现，遍历u的出边时，如果更新u的dp值更新到一半，假设要更新vi这个儿子那么此时min\[u]的值是min\[v1]\~min\[vi-1]的最小值，所以我们可以用min\[vi]+min\[u]更新一发答案，最大值同理的可以如此更新 然后说比较辣手的sum 可能需要一点数学证明 假设点v1,v2的父亲都是u 有一个以v1为根的子树，里边询问点q1,q2,……qi到u的路径长度记为 a1,a2……ai，又有一个以v2为根的子树，里边询问点p1,p2……pi到u的路径长度记为b1,b2……bi， 那么v1中的询问点到v2中询问点的路径长度之和就是 sigma(sigma(ai+bj) \[j∈1~siz\[v2]] ) \[i∈1~siz\[v1]] =(sum\[v1]+dis(v1,u))\*siz\[v2]+(sum\[v2]+dis(v2,u))\*siz\[v1] 就是v1里的每一条路径被统计了siz\[v2]次，v2中的每一条路径被统计了siz\[v1]次 那么我们现在有了一个合并sum\[v1]，sum\[v2]的公式，现在我们要合并u的所有儿子v1,v2,……vi 我们还是考虑dp到了一半的时候，我们现在要更新vi这个儿子，那么sum\[u]其实是sum\[v1]~sum\[vi-1]的和，siz\[u]其实是siz\[v1]~siz\[vi-1]的和，那么我们的v1要和前面的每一个孩子合并一次，利用乘法分配率可得： 答案+=siz\[u]\*(sum\[vi]+dis(vi,u))+siz\[vi]\*sum\[u] 好了现在sum也可以更新了 现在是最后的问题，如何在虚树上dfs？,总不能n^2枚举每个点连边吧，另外空间存储也会很烦，如果你去网上搜索的话，你会发现他们维护了一个什么最右链，像扫描线一样把整只虚树扫了一遍，起到了dfs的效果(蒟蒻表示不会QAQ) 所以这里给大家介绍一个暴力的方法：回想一下dfs的时候，计算机到底干了什么，其实是开了一个栈，按照给定的指令不停pushpop对吧，那么如果我们不知道树的结构，但是却知道dfs的时候什么时候push和pop什么点，再给我们一个栈，我们就可以在不知道树的真实结构的情况下dfs。 这里安利一个叫欧拉序的好东西，普通的dfs序只记录入栈时间，但是欧拉序同时记录入栈和出栈时间，入栈为+，出栈为-，事实上，我们只要手里有欧拉序就可以dfs，我们发现，虚树和原树的dfs相对次序是完全一样的，因此，我们先把询问点dfs序排序一遍，之后求出lca，最后把整个点集按照欧拉序排序(记得一个点加两次)，我们就得到了虚树的欧拉序，开个栈暴力dfs一一边即可，也就是说，虚树的本质，就是每次在原树上进行部分的dfs (复杂度NlogN？第一如果你不嫌麻烦可以基数排序+TARJAN离线lca，第二如果你用的是快排+倍增lca的话一堆nlogn加起来比总共的nlogn会小很多，第三就算卡你4s的时限也是随便过) 上代码~ ```C #include<cstdio> #include<algorithm> #include<vector> #include<stack> using namespace std; typedef long long ll; const int N=1000010; int n;int m; struct data{int v;int nxt;}edge[2*N]; int alist[N];int cnt; inline void add(int u,int v){edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;} int dfin[N];int dfou[N];int dfu;int fa[22][N];bool book[N];ll dep[N]; void dfs(int x) { for(int i=0;fa[i][x];i++){fa[i+1][x]=fa[i][fa[i][x]];}//倍增预处理 dfin[x]=++dfu;book[x]=true;int nxt=alist[x];//记录入栈顺序 while(nxt) { int v=edge[nxt].v; if(!book[v]){dep[v]=dep[x]+1;fa[0][v]=x;dfs(v);} nxt=edge[nxt].nxt; }dfou[x]=++dfu;return;//记录出栈顺序 } inline int lca(int x,int y)//倍增求lca { if(dep[x]<dep[y])swap(x,y);int del=dep[x]-dep[y]; for(int i=0;del;del>>=1,i++){if(del&1)x=fa[i][x];}if(x==y){return x;} for(int i=21;i>=0;i--){if(fa[i][x]!=fa[i][y]){x=fa[i][x],y=fa[i][y];}} return fa[0][x]; } inline bool cmp(int x,int y)//按欧拉序排序的比较函数 { int key1=(x>0)?dfin[x]:dfou[-x]; int key2=(y>0)?dfin[y]:dfou[-y]; return key1<key2; } int tp[4*N];ll sum[N];ll siz[N];ll mi[N];ll ma[N];bool vis[N]; ll tot[N];stack <int> s; int main() { scanf("%d",&n); for(int i=1;i<n;i++){int u;int v;scanf("%d%d",&u,&v);add(u,v);add(v,u);} dfs(1);//先预处理 scanf("%d",&m); for(int i=1;i<=n;i++){mi[i]=0x7f7f7f7f7f;} for(int i=1;i<=m;i++) { ll ans1=0;ll ans2=0x7f7f7f7f7f;ll ans3=0; int k;scanf("%d",&k);int cnt=k; for(int i=1;i<=k;i++) {scanf("%d",&tp[i]);mi[tp[i]]=0;siz[tp[i]]=1;vis[tp[i]]=true;}//处理dp的边界条件 sort(tp+1,tp+k+1,cmp);tp[++cnt]=-tp[1];//这里先按dfs序排一波 for(int i=2;i<=k;i++) { int lc=lca(tp[i],tp[i-1]);tp[++cnt]=-tp[i];//计算lca，每一个点正负各插一遍 if(!vis[lc]){tp[++cnt]=lc;tp[++cnt]=-lc;vis[lc]=true;} } sort(tp+1,tp+cnt+1,cmp);//强行求出欧拉序 for(int i=1;i<=cnt;i++) { if(tp[i]>0){s.push(tp[i]);continue;}//无脑入栈 if(tp[i]<0) { int now=s.top();s.pop();//出栈的话，这个点和当前栈顶肯定是父子关系，开始dp if(!s.empty())//特判下pop根的情况 { int to=s.top();ll dis=(dep[now]-dep[to]);//计算dis sum[now]+=siz[now]*dis;//所有路径拔高 ans1+=siz[to]*sum[now]+siz[now]*sum[to];//更新答案 siz[to]+=siz[now];sum[to]+=sum[now];//更新sum mi[now]+=dis;ans2=min(ans2,mi[to]+mi[now]);mi[to]=min(mi[to],mi[now]);//更新min ma[now]+=dis;ans3=max(ans3,ma[to]+ma[now]);ma[to]=max(ma[to],ma[now]);//更新max } siz[now]=0;sum[now]=0;mi[now]=0x7f7f7f7f7f;ma[now]=0;vis[now]=false;//出栈的时候记得清空信息 } } printf("%lld %lld %lld\n",ans1,ans2,ans3);//输出答案 }return 0;//拜拜程序~ } ```