六安网站/企业推广托管
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
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
6 6 6
1 1 1
2 2 2
2 2 2
HINT
n<=1000000
q<=50000并且保证所有k之和<=2*n
Source
鸣谢佚名上传
虚树+树DP
对于每次询问建立虚树
然后树DP的时候，记录经过该点的最长，次长，最短，次短链。
更新最短答案的时候判断当前点是否为询问点，是的话直接左右找最短，否则左右最短加次短
更新最大答案的时候直接最长加次长
更新总和的时候枚举每个孩子，看该孩子中有多少关键点，统计这些关键点对其他子树上的链的贡献即可
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
struct line
{int s,t;long long x;int next;
}a[2000001],exa[2000001];
int head[1000001],exhead[1000001];
int edge,exedge;
inline void add(int s,int t,long long x)
{a[edge].next=head[s];head[s]=edge;a[edge].s=s;a[edge].t=t;a[edge].x=x;
}
inline void exadd(int s,int t,long long x)
{exa[exedge].next=exhead[s];exhead[s]=exedge;exa[exedge].s=s;exa[exedge].t=t;exa[exedge].x=x;
}
bool v[1000001];
int dep[1000001];
int ans[1000001][22];
long long anc[1000001][22];
queue<int> Q,Q1;
inline void bfs(int r)
{int i,j;dep[r]=1;for(i=0;i<=21;i++)ans[r][i]=r;while(!Q.empty())Q.pop();Q.push(r);v[r]=true;while(!Q.empty()){int d=Q.front();Q.pop();for(i=head[d];i!=0;i=a[i].next){int t=a[i].t;if(!v[t]){v[t]=true;Q.push(t);dep[t]=dep[d]+1;ans[t][0]=d;anc[t][0]=a[i].x;int dt;long long dc;for(j=1;j<=21;j++){dt=ans[t][j-1];dc=anc[t][j-1];ans[t][j]=ans[dt][j-1];dc+=anc[dt][j-1];anc[t][j]=dc;}}}}
}
long long ansx;
inline int swim(int x,int y)
{int i=21; while(dep[x]!=dep[y]){while(dep[ans[y][i]]<dep[x])i--;ansx+=anc[y][i];y=ans[y][i];}return y;
}
inline long long lca(int x,int y)
{ansx=0;if(dep[x]>dep[y]){int t=x;x=y;y=t;}y=swim(x,y);int i=21;while(x!=y){while(ans[x][i]==ans[y][i]&&i!=0)i--;ansx+=anc[x][i];ansx+=anc[y][i];x=ans[x][i];y=ans[y][i];}return x;
}
int tot;
int ld[1000001],rd[1000001];
inline void dfs(int d)
{tot++;ld[d]=tot;v[d]=true;int i;for(i=head[d];i!=0;i=a[i].next){int t=a[i].t;if(!v[t])dfs(t);}rd[d]=tot;
}
int poi[1000001],stak[1000001];
bool mark[1000001],vx[1000001];
int rt;
inline bool cmp(int x,int y)
{return ld[x]<ld[y];
}
inline void create(int k)
{int i,j,lc;int top=0;top++;stak[top]=poi[1];exedge=0;exhead[poi[1]]=0;for(i=2;i<=k;i++){lc=lca(stak[top],poi[i]);if(lc==stak[top]){exhead[poi[i]]=0;top++;stak[top]=poi[i];if(dep[poi[i]]<dep[rt])rt=poi[i];}else{int tmp=top;while(tmp>0&&dep[stak[tmp]]>dep[lc])tmp--;tmp++;for(j=tmp;j<=top-1;j++){lca(stak[j],stak[j+1]);exedge++;exadd(stak[j],stak[j+1],ansx);exedge++;exadd(stak[j+1],stak[j],ansx);}int pretmp=stak[tmp];if(tmp==0){exhead[lc]=0;top=1;stak[top]=lc;if(dep[lc]<dep[rt])rt=lc;}else if(stak[tmp-1]!=lc){exhead[lc]=0;// tmp++;stak[tmp]=lc;top=tmp;if(dep[lc]<dep[rt])rt=lc;}elsetop=tmp-1;lca(pretmp,lc);exedge++;exadd(pretmp,lc,ansx);exedge++;exadd(lc,pretmp,ansx);exhead[poi[i]]=0;top++;stak[top]=poi[i];if(dep[poi[i]]<dep[rt])rt=poi[i];}}for(i=1;i<=top-1;i++){lca(stak[i],stak[i+1]);exedge++;exadd(stak[i],stak[i+1],ansx);exedge++;exadd(stak[i+1],stak[i],ansx);}
}
long long sum[1000001];
long long sx[1000001],sx1[1000001],sx2[1000001],sx3[1000001],sx4[1000001];
inline void trdp(int d)
{bool flag=false;Q.push(d);Q1.push(d);sum[d]=0;sx[d]=0;sx1[d]=2100000000;sx2[d]=0;sx3[d]=0;sx4[d]=2100000000;v[d]=true;int i;for(i=exhead[d];i!=0;i=exa[i].next){int t=exa[i].t;if(!v[t]){flag=true;trdp(t);sx[d]+=sum[t]*exa[i].x+sx[t];sum[d]+=sum[t];if(sx2[t]+exa[i].x>sx2[d]){sx3[d]=sx2[d];sx2[d]=sx2[t]+exa[i].x;}else if(sx2[t]+exa[i].x>sx3[d])sx3[d]=sx2[t]+exa[i].x;if(!mark[t]){if(sx1[t]+exa[i].x<sx1[d]){sx4[d]=sx1[d];sx1[d]=sx1[t]+exa[i].x;}else if(sx1[t]+exa[i].x<sx4[d])sx4[d]=sx1[t]+exa[i].x;}else{if(exa[i].x<sx1[d]){sx4[d]=sx1[d];sx1[d]=exa[i].x;}else if(exa[i].x<sx4[d])sx4[d]=exa[i].x;}}}if(mark[d])sum[d]++;if(!flag){sx1[d]=0;sx4[d]=0;}
}
long long ans1,ans2,ans3;
inline void dfsx(int d)
{v[d]=true;int i;long long sumx=0;bool flag=false;for(i=exhead[d];i!=0;i=exa[i].next){int t=exa[i].t;if(!v[t]){flag=true;dfsx(t);sumx+=(sx[d]-sx[t]-sum[t]*exa[i].x)*sum[t];if(mark[d])sumx+=sx[t]+sum[t]*exa[i].x;}}ans1+=sumx;if(flag){if(mark[d])ans2=min(ans2,sx1[d]);elseans2=min(ans2,sx1[d]+sx4[d]);}ans3=max(ans3,sx2[d]+sx3[d]);
}
inline void getans()
{ans1=0,ans2=2100000000,ans3=0;dfsx(rt);printf("%lld %lld %lld\n",ans1,ans2,ans3);
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);int n;scanf("%d",&n);int i,j;int s,t;long long x;for(i=1;i<=n-1;i++){scanf("%d%d",&s,&t);edge++;add(s,t,1);edge++;add(t,s,1);}bfs(1);memset(v,false,sizeof(v));dfs(1);int m,k;scanf("%d",&m);memset(v,false,sizeof(v));memset(vx,false,sizeof(vx));memset(mark,0,sizeof(mark));for(i=1;i<=m;i++){scanf("%d",&k);for(j=1;j<=k;j++){scanf("%d",&poi[j]);mark[poi[j]]=1;}sort(poi+1,poi+1+k,cmp);rt=poi[1];create(k);trdp(rt);while(!Q1.empty()){v[Q1.front()]=false;Q1.pop();}getans();while(!Q.empty()){v[Q.front()]=false;Q.pop();}for(j=1;j<=k;j++)mark[poi[j]]=0;}return 0;
}