国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
第一行 n 表示点数。
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
n<=1000000
又是一道虚树上DP。
建虚树时边权不该是1，而是dep的差值。
对于询问最近点对和最远点对DP很简单。只需要dp到x时统计以x为lca的点对之间的距离来更新答案。具体来说，设f[x]表示以x为根的子树中到x最远的标记点的距离，g[x]表示最近的，转移看code，很简单的。
至于统计两两点对的距离和，考虑计算每条边会被经过的次数，应该是它两端标记点个数的积，乘以边权就是这条边的贡献，所有边的贡献和就是答案（这好像都成一个套路了……）。
注意一下距离和要开longlong，DP各个变量的初值要对，然后写起来还是很顺畅的~
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e6+5,INF=0x3f3f3f3f; inline int read(){ int x=0,w=0;char ch=0; while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return w?-x:x; } struct edge{ int v,last; }e[N<<1]; int tot,tail[N]; inline void add1(int x,int y){ e[++tot]=(edge){y,tail[x]}; tail[x]=tot; } inline void add2(int x,int y){ add1(x,y),add1(y,x); } int idx,dfn[N],dep[N],d[N],low[N],fa[N][21]; void dfs(int x,int pre){ dfn[x]=++idx;dep[x]=dep[pre]+1;fa[x][0]=pre; for(int i=1;;++i) if(fa[x][i-1]) fa[x][i]=fa[fa[x][i-1]][i-1]; else break; for(int p=tail[x];p;p=e[p].last){ int &v=e[p].v; if(v==pre) continue; dfs(v,x); } low[x]=idx; } int LCA(int x,int y){ if(dep[x]<dep[y]) x^=y^=x^=y; for(int i=20;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;i>=0;--i) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } bool tag[N]; LL ans3; int n,m,k,cnt,ans1,ans2,f[N],g[N],sz[N],st[N<<1],a[N<<1]; void dp(int x){ sz[x]=tag[x],f[x]=0,g[x]=tag[x]?0:INF; for(int p=tail[x];p;p=e[p].last){ int &v=e[p].v,w=dep[v]-dep[x]; dp(v); if(sz[x]>0) ans1=max(ans1,f[x]+w+f[v]), ans2=min(ans2,g[x]+w+g[v]); ans3+=w*(1ll*sz[v]*(cnt-sz[v])); f[x]=max(f[x],w+f[v]); g[x]=min(g[x],w+g[v]); sz[x]+=sz[v]; } tag[x]=0;tail[x]=0; } bool cmp(int x,int y){return dfn[x]<dfn[y];} int main(){ n=read(); for(int i=1;i<n;++i) add2(read(),read()); dfs(1,0); m=read(); tot=0;memset(tail,0,sizeof tail); while(m--){ tot=ans1=ans3=0;ans2=INF; k=cnt=read(); for(int i=1;i<=k;++i) a[i]=read(),tag[a[i]]=true; a[++k]=1; //手动添加1号节点 sort(a+1,a+k+1,cmp); for(int i=k;i>1;--i) a[++k]=LCA(a[i],a[i-1]); sort(a+1,a+k+1,cmp); k=unique(a+1,a+k+1)-a-1; for(int i=1,tp=0;i<=k;++i){ while(tp&&low[st[tp]]<dfn[a[i]]) --tp; if(tp) add1(st[tp],a[i]); st[++tp]=a[i]; } dp(1); cout<<ans3<<‘ ‘<<ans2<<‘ ‘<<ans1<<endl; } return 0; }
[BZOJ3611][Heoi2014]大工程（虚树上DP）
原文：https://www.cnblogs.com/gosick/p/11255382.html
