国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
第一行 n 表示点数。
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
n<=1000000
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 1000005 7 #define inf 1061109567 8 using namespace std; 9 typedef long long int64; 10 char ch; 11 bool ok; 12 void read(int &x){ 13 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch==‘-‘) ok=1; 14 for (x=0;isdigit(ch);x=x*10+ch-‘0‘,ch=getchar()); 15 if (ok) x=-x; 16 } 17 int n,q,a,b,k; 18 int idx,fa[maxn][21],dfn[maxn],dis[maxn],cnt,top,list[maxn],stack[maxn],bo[maxn]; 19 int ans1,ans2,siz[maxn],g[2][maxn]; 20 int64 f[maxn]; 21 bool cmp(int a,int b){return dfn[a]<dfn[b];} 22 struct Graph{ 23 int tot,now[maxn],son[maxn<<1],pre[maxn<<1]; 24 void init(){tot=0,memset(now,0,sizeof(now));} 25 inline void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;} 26 inline void dfs1(int u){ 27 dfn[u]=++idx; 28 for (int i=0;fa[u][i];i++) fa[u][i+1]=fa[fa[u][i]][i]; 29 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) 30 if (v!=fa[u][0]) fa[v][0]=u,dis[v]=dis[u]+1,dfs1(v); 31 } 32 inline void dfs2(int u){ 33 siz[u]=bo[u]; 34 f[u]=0,g[0][u]=inf,g[1][u]=0; 35 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]){ 36 dfs2(v),siz[u]+=siz[v]; 37 int d=dis[v]-dis[u]; 38 f[u]+=f[v]+1LL*siz[v]*(k-siz[v])*d; 39 ans1=min(ans1,g[0][u]+g[0][v]+d),ans2=max(ans2,g[1][u]+g[1][v]+d); 40 g[0][u]=min(g[0][u],g[0][v]+d); 41 g[1][u]=max(g[1][u],g[1][v]+d); 42 } 43 if (bo[u]) ans1=min(ans1,g[0][u]),ans2=max(ans2,g[1][u]),g[0][u]=0; 44 now[u]=0; 45 } 46 }G1,G2; 47 void swim(int &u,int h){for (int i=20;h;i--) if (h>=(1<<i)) h-=(1<<i),u=fa[u][i];} 48 int calc_lca(int u,int v){ 49 if (dis[u]<dis[v]) swap(u,v); 50 swim(u,dis[u]-dis[v]); 51 if (u==v) return u; 52 for (int i=20;i>=0;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; 53 return fa[u][0]; 54 } 55 int main(){ 56 read(n); 57 for (int i=1;i<n;i++) read(a),read(b),G1.put(a,b),G1.put(b,a); 58 G1.dfs1(1); 59 for (read(q);q;q--){ 60 read(k),cnt=top=0; 61 for (int i=1;i<=k;i++) read(list[i]),bo[list[i]]=1; 62 sort(list+1,list+k+1,cmp); 63 for (int i=1;i<=k;i++){ 64 if (!top){stack[++top]=list[i];continue;} 65 int lca=calc_lca(stack[top],list[i]); 66 while (dfn[lca]<dfn[stack[top]]){ 67 if (dfn[lca]>=dfn[stack[top-1]]){ 68 G2.put(lca,stack[top]); 69 if (stack[--top]!=lca) stack[++top]=lca; 70 break; 71 } 72 G2.put(stack[top-1],stack[top]),top--; 73 } 74 stack[++top]=list[i]; 75 } 76 while (top>1) G2.put(stack[top-1],stack[top]),top--; 77 ans1=inf,ans2=0; 78 G2.dfs2(stack[1]); 79 printf("%lld %d %d\n",f[stack[1]],ans1,ans2); 80 for (int i=1;i<=k;i++) bo[list[i]]=0; 81 G2.tot=0; 82 } 83 return 0; 84 }
原文：http://www.cnblogs.com/chenyushuo/p/5069169.html