题目
题目描述
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
输入输出格式
输入格式：
第一行 n 表示点数。
接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。点从 1 开始标号。
接下来一行 q 表示计划数。对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
输出格式：
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
输入输出样例
输入样例#1：
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
输出样例#1：
3 3 3
6 6 6
1 1 1
2 2 2
2 2 2
说明
对于第 1,2 个点: n<=10000
对于第 3,4,5 个点: n<=100000,交通网络构成一条链
对于第 6,7 个点: n<=100000
对于第 8,9,10 个点: n<=1000000
对于所有数据, q<=50000并且保证所有k之和<=2*n
题解
强行三合一？
首先建好虚树，对于每个要求的答案
- 求边权和，可以枚举每条边，答案就是$\sum_{i=1}^{k-1}size_{x_i}\times size_{y_i}\times dis(x_i,y_i)$，$dfs$一遍处理出来子树大小即可
- 求最小边权，可以树上$dp$，$f1_i,f2_i$表示$i$到子树中最近和第二近的关键点的距离，如果是关键点，$ans=min(ans,f1_i)$，否则$ans=min(ans,f1_i+f2_i)$
- 求最大边权，就是求树上关键点之间的直径……几遍$dfs$找即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e6+5;
struct p{
int x,y,dis;
}c[MAX<<1],cc[MAX];
int n,m,num,Top,cnt,ID,maxn,Num,minn;
LL ans;
int h[MAX],T[MAX],siz[MAX],son[MAX],fa[MAX],id[MAX],d[MAX],top[MAX],D[MAX],st[MAX],F1[MAX],F2[MAX];
bool use[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int cmp(int a,int b) {return id[a]<id[b];}
void add(int x,int y,int dis=1)
{
cc[++Num]=(p){x,y,dis};
c[++num]=(p){h[x],y,dis},h[x]=num;
c[++num]=(p){h[y],x,dis},h[y]=num;
}
void dfs(int x=1,int F=0)
{
fa[x]=F,d[x]=d[F]+(siz[x]=1);
for(int i=h[x];i;i=c[i].x)
if(c[i].y^F)
{
dfs(c[i].y,x),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,id[x]=++cnt;
if(!son[x]) return void(h[x]=0);
dfs1(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if((c[i].y^fa[x])&&(c[i].y^son[x])) dfs1(c[i].y,c[i].y);
h[x]=0;
}
void Dfs(int x=1,int fa=0,int dis=0)
{
D[x]=D[fa]+dis,siz[x]=0;
if(use[x])
{
siz[x]=1;
if(D[x]>maxn) maxn=D[x],ID=x;
}
for(int i=h[x];i;i=c[i].x)
if(c[i].y^fa) Dfs(c[i].y,x,c[i].dis),siz[x]+=siz[c[i].y];
}
void Dfs_(int x=1,int fa=0,int dis=0)
{
D[x]=D[fa]+dis;
if(use[x]&&D[x]>maxn) maxn=D[x],ID=x;
for(int i=h[x];i;i=c[i].x)
if(c[i].y^fa) Dfs_(c[i].y,x,c[i].dis);
h[x]=use[x]=0,F1[x]=F2[x]=1e9;
}
void Dfs__(int x=1,int fa=0,int dis=0)
{
bool fl=0;
D[x]=D[fa]+dis,siz[x]=0;
if(use[x])
{
siz[x]=1;
if(D[x]>maxn) maxn=D[x],ID=x;
}
for(int i=h[x];i;i=c[i].x)
if(c[i].y^fa)
{
fl=1,Dfs__(c[i].y,x,c[i].dis),siz[x]+=siz[c[i].y];
if(F1[x]>F1[c[i].y]+c[i].dis) F2[x]=F1[x],F1[x]=F1[c[i].y]+c[i].dis;
else if(F2[x]>F1[c[i].y]+c[i].dis) F2[x]=F1[c[i].y]+c[i].dis;
}
if(fl)
{
if(!use[x]) minn=min(minn,F1[x]+F2[x]);
else minn=min(minn,F1[x]);
}
if(use[x]) F1[x]=0;
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
return d[x]>d[y]?y:x;
}
int GET_DIS(int x,int y) {return d[x]+d[y]-(d[LCA(x,y)]<<1);}
void Work(int k)
{
maxn=num=Num=ans=0,st[Top=1]=1,minn=1e9;
for(int i=1,lca,x;i<=k;++i)
{
lca=LCA(st[Top],T[i]);
while(Top>1&&d[lca]<d[st[Top-1]]) add(st[Top],st[Top-1],GET_DIS(st[Top],st[Top-1])),--Top;
while(Top&&d[lca]<d[st[Top]]) add(lca,st[Top],GET_DIS(lca,st[Top])),--Top;
if(!Top||d[lca]>d[st[Top]]) st[++Top]=lca;
if(st[Top]!=T[i]) st[++Top]=T[i];
}
while(Top>1) add(st[Top],st[Top-1],GET_DIS(st[Top],st[Top-1])),--Top;
Dfs__();
for(int i=1;i<=Num;++i)
{
if(D[cc[i].x]<D[cc[i].y]) swap(cc[i].x,cc[i].y);
ans+=1ll*cc[i].dis*siz[cc[i].x]*(k-siz[cc[i].x]);
}
maxn=0,Dfs(ID),maxn=0,maxn=0,Dfs_(ID),printf("%lld %d %d\n",ans,minn,maxn);
}
int main()
{
n=read();
memset(F1,1,sizeof(F1)),memset(F2,1,sizeof(F2));
for(int i=1,x;i<n;++i)
x=read(),add(x,read());
dfs(),dfs1(),m=read();
for(int i=1,k;i<=m;++i)
{
k=read();
for(int j=1;j<=k;++j)
use[T[j]=read()]=1;
sort(T+1,T+1+k,cmp),Work(k);
}
return 0;
}
