[虚树][树形dp] Bzoj P3611 大工程

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

题解

也像上一题消耗战一样，构造出虚树上树形dp就好了

代码

 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
",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 }