Description
国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划,我们想知道:
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
Input
第一行 n 表示点数。
接下来 n-1 行,每行两个数 a,b 表示 a 和 b 之间有一条边。
点从 1 开始标号。 接下来一行 q 表示计划数。
对每个计划有 2 行,第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
Output
输出 q 行,每行三个数分别表示代价和,最小代价,最大代价。
Sample Input
10
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
2
5 4
2
10 4
2
5 2
2
6 1
2
6 1
Sample Output
3 3 3
6 6 6
1 1 1
2 2 2
2 2 2
HINT
n<=1000000
q<=50000并且保证所有k之和<=2*n
题解
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 #define N 1000010
8 #define ll long long
9 #define inf 0x3fffffff
10 using namespace std;
11 int cnt,n,m,k,head[N],last[N],dep[N],fa[N][20],size[N],mx[N],mn[N],ans2,ans3,tim,dfn[N],logn,a[N],flag[N],st[N];
12 ll sum[N],ans1;
13 struct edge{int to,from;}e[N*2];
14 void insert1(int u,int v)
15 {
16 e[++cnt].to=v,e[cnt].from=head[u],head[u]=cnt;
17 e[++cnt].to=u,e[cnt].from=head[v],head[v]=cnt;
18 }
19 void insert2(int u,int v)
20 {
21 if (u==v) return;
22 e[++cnt].to=v,e[cnt].from=last[u],last[u]=cnt;
23 }
24 void dfs(int x)
25 {
26 dfn[x]=++tim;
27 for (int i=1;i<=logn;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
28 dep[x]=dep[fa[x][0]]+1;
29 for (int i=head[x];i;i=e[i].from) if (e[i].to!=fa[x][0]) fa[e[i].to][0]=x,dfs(e[i].to);
30 }
31 int getlca(int x,int y)
32 {
33 if (dep[x]<dep[y]) swap(x,y);
34 for (int i=logn;i>=0;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
35 if (x==y) return x;
36 for (int i=logn;i>=0;i--) if (fa[x][0]!=fa[y][0]) x=fa[x][0],y=fa[y][0];
37 return fa[x][0];
38 }
39 bool cmp(int a,int b) { return dfn[a]<dfn[b]; }
40 void dp(int x)
41 {
42 int mx1=0,mx2=0,mn1=inf,mn2=inf;size[x]=0;sum[x]=0;
43 if (flag[x]) size[x]++,sum[x]=dep[x],mn1=0;
44 for (int i=last[x];i;i=e[i].from)
45 {
46 dp(e[i].to);
47 size[x]+=size[e[i].to];sum[x]+=sum[e[i].to];
48 if (mx[e[i].to]+dep[e[i].to]-dep[x]>mx1) mx2=mx1,mx1=mx[e[i].to]+dep[e[i].to]-dep[x];
49 else if (mx[e[i].to]+dep[e[i].to]-dep[x]>mx2) mx2=mx[e[i].to]+dep[e[i].to]-dep[x];
50 if (mn[e[i].to]+dep[e[i].to]-dep[x]<mn1) mn2=mn1,mn1=mn[e[i].to]+dep[e[i].to]-dep[x];
51 else if (mn[e[i].to]+dep[e[i].to]-dep[x]<mn2) mn2=mn[e[i].to]+dep[e[i].to]-dep[x];
52 }
53 for (int i=last[x];i;i=e[i].from) ans1+=(ll)(size[x]-size[e[i].to])*(sum[e[i].to]-(ll)size[e[i].to]*dep[x]);
54 ans2=min(ans2,mn1+mn2);
55 if (flag[x]||!flag[x]&&mx2) ans3=max(ans3,mx1+mx2);
56 mx[x]=mx1;mn[x]=mn1,last[x]=0;
57 }
58 void solve()
59 {
60 cnt=0,scanf("%d",&k);
61 for (int i=1;i<=k;i++) scanf("%d",&a[i]),flag[a[i]]=1;
62 sort(a+1,a+k+1,cmp);
63 int top=1; st[1]=1;
64 for (int i=1;i<=k;i++)
65 {
66 int now=a[i],f=getlca(now,st[top]);
67 while (1)
68 {
69 if (dep[f]>=dep[st[top-1]])
70 {
71 insert2(f,st[top]),top--;
72 if (st[top]!=f) st[++top]=f;
73 break;
74 }
75 insert2(st[top-1],st[top]),top--;
76 }
77 if (st[top]!=now) st[++top]=now;
78 }
79 while (top>1) insert2(st[top-1],st[top]),top--;
80 ans1=ans3=0;ans2=inf,dp(1);
81 for (int i=1;i<=k;i++) flag[a[i]]=0;
82 printf("%lld %d %d\n",ans1,ans2,ans3);
83 }
84 int main()
85 {
86 freopen("data.in","r",stdin);
87 scanf("%d",&n);
88 for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),insert1(x,y);
89 logn=log(n)/log(2),dfs(1),scanf("%d",&m);
90 for (int i=1;i<=m;i++) solve();
91 }
原文:https://www.cnblogs.com/Comfortable/p/11136797.html