题面
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
分析
显然需要建虚树，我们考虑如何在虚树上DP（注意：以下定义的点和子树都是虚树上的）
设sz[x]表示x的子树内有多少个询问点,sum[x]表示x子树内的路径长度和，dmin[x]表示x子树内到x的最小路径长度，dmax[x]表示 x子树内到x的最大路径长度
对于x的子节点y,我们可以写出如下的状态转移方程
sum[x]+=sum[y]+(k-sz[y]) · sz[y] ·dist(x,y)
x的子树内的路径分为两种：一种是在y的子树内部的路径，一种是从y的子树内的sz[y]个节点到子树外(k-sz[y])个节点)
dmin[x]=min(dmin[x],dmin[y]+dist(x,y));
dmax[x]=max(dmax[x],dmax[y]+dist(x,y));
long long siz[maxn];//siz[x],x子树内询问点的个数
long long sum[maxn],dmin[maxn],dmax[maxn];
//sum[x] x子树内的路径长度和
//dmin[x] x子树内到x的最小路径长度
//dmax[x] x子树内到x的最大路径长度
long long ans_sum,ans_min,ans_max;
void dfs2(int x,int fa){
siz[x]=is_q[x];
dmax[x]=0;
dmin[x]=INF;
sum[x]=0;
for(int i=T2.head[x];i;i=T2.E[i].next){
int y=T2.E[i].to;
long long len=deep[y]-deep[x];
if(y!=fa){
dfs2(y,x);
sum[x]+=sum[y]+siz[y]*(k-siz[y])*len;
//y子树内部路径 + y子树到外面其他询问点的路径
siz[x]+=siz[y];
ans_min=min(ans_min,dmin[x]+dmin[y]+len);
ans_max=max(ans_max,dmax[x]+dmax[y]+len);
dmin[x]=min(dmin[x],dmin[y]+len);
dmax[x]=max(dmax[x],dmax[y]+len);
}
}
if(is_q[x]){
ans_min=min(ans_min,dmin[x]);
ans_max=max(ans_max,dmax[x]);
dmin[x]=0;//当前最小值为0，这样祖先节点就可以用它来更新最小值（最小路径可能是祖先~x）
}
T2.head[x]=0;
}
注意，此题需要卡常
可以预处理出2的i次方，然后在lca里面优化倍增，详情见代码
代码
//http://119.29.55.79/problem/276
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 1000005
#define maxlog 32
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline void qread(int &x){
x=0;
int sign=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
x=x*sign;
}
inline void qprint(long long x){
if(x<0){
putchar('-');
qprint(-x);
}else if(x==0){
putchar('0');
return;
}else{
if(x/10>0) qprint(x/10);
putchar('0'+x%10);
}
}
int n,m;
struct graph{
struct edge{
int from;
int to;
int next;
}E[maxn<<1];
int head[maxn];
int sz;
void add_edge(int u,int v){
sz++;
E[sz].from=u;
E[sz].to=v;
E[sz].next=head[u];
head[u]=sz;
sz++;
E[sz].from=v;
E[sz].to=u;
E[sz].next=head[v];
head[v]=sz;
}
graph(){
sz=1;
}
}T1,T2;
int log2n;
int tim=0;
int dfn[maxn];
int deep[maxn];
int bin[maxn];//卡常用
int anc[maxn][maxlog];
void dfs1(int x,int fa){
dfn[x]=++tim;
deep[x]=deep[fa]+1;
anc[x][0]=fa;
for(int i=1;bin[i]<=deep[x];i++)anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=T1.head[x];i;i=T1.E[i].next){
int y=T1.E[i].to;
if(y!=fa){
dfs1(y,x);
}
}
}
int lca(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;bin[i]<=t;i++){
if(bin[i]&t){
x=anc[x][i];
}
}
if(x==y) return x;
for(int i=log2n;i>=0;i--){
if(anc[x][i]!=anc[y][i]){
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
int k;
int top=0;
int s[maxn];
int in[maxn];
int cmp(int x,int y){
return dfn[x]<dfn[y];
}
int is_q[maxn];//是否是询问点
void insert(int x){
if(top<=1){
s[++top]=x;
return;
}
int lc=lca(x,s[top]);
if(lc==s[top]){
s[++top]=x;
return;
}
while(top>1&&deep[s[top-1]]>=deep[lc]){
T2.add_edge(s[top-1],s[top]);
// printf("vtree : %d->%d
",s[top-1],s[top]);
top--;
}
if(s[top]!=lc){
T2.add_edge(lc,s[top]);
// printf("vtree : %d->%d
",lc,s[top]);
}
s[top]=lc;
s[++top]=x;
}
long long siz[maxn];//siz[x],x子树内询问点的个数
long long sum[maxn],dmin[maxn],dmax[maxn];
//sum[x] x子树内的路径长度和
//dmin[x] x子树内到x的最小路径长度
//dmax[x] x子树内到x的最大路径长度
long long ans_sum,ans_min,ans_max;
void dfs2(int x,int fa){
siz[x]=is_q[x];
dmax[x]=0;
dmin[x]=INF;
sum[x]=0;
for(int i=T2.head[x];i;i=T2.E[i].next){
int y=T2.E[i].to;
long long len=deep[y]-deep[x];
if(y!=fa){
dfs2(y,x);
sum[x]+=sum[y]+siz[y]*(k-siz[y])*len;
//y子树内部路径 + y子树到外面其他询问点的路径
siz[x]+=siz[y];
ans_min=min(ans_min,dmin[x]+dmin[y]+len);
ans_max=max(ans_max,dmax[x]+dmax[y]+len);
dmin[x]=min(dmin[x],dmin[y]+len);
dmax[x]=max(dmax[x],dmax[y]+len);
}
}
if(is_q[x]){
ans_min=min(ans_min,dmin[x]);
ans_max=max(ans_max,dmax[x]);
dmin[x]=0;//当前最小值为0，这样祖先节点就可以用它来更新最小值（最小路径可能是祖先~x）
}
T2.head[x]=0;
}
void solve(){
sort(in+1,in+1+k,cmp);
for(int i=1;i<=k;i++) is_q[in[i]]=1;
int root=lca(in[1],in[2]);
for(int i=3;i<=k;i++){
root=lca(root,in[i]);
}
top=0;
s[++top]=root;
for(int i=1;i<=k;i++){
if(in[i]!=root)insert(in[i]);
}
while(top>1){
T2.add_edge(s[top-1],s[top]);
// printf("vtree : %d->%d
",s[top-1],s[top]);
top--;
}
ans_sum=0;
ans_max=0;
ans_min=INF;
dfs2(root,0);
ans_sum=sum[root];
for(int i=1;i<=k;i++) is_q[in[i]]=0;
T2.sz=1;
}
int main(){
#ifdef FILE_IO
freopen("tree9.in","r",stdin);
freopen("tree9.ans","w",stdout);
#endif
int u,v;
qread(n);
log2n=log2(n)+1;
bin[0]=1;
for(int i=1;i<=log2n;i++) bin[i]=bin[i-1]*2;
for(int i=1;i<n;i++){
qread(u);
qread(v);
T1.add_edge(u,v);
}
dfs1(1,0);
qread(m);
for(int i=1;i<=m;i++){
qread(k);
for(int j=1;j<=k;j++){
qread(in[j]);
}
solve();
qprint(ans_sum);putchar(' ');
qprint(ans_min);putchar(' ');
qprint(ans_max);putchar('
');
}
}