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
Solution
其实这个题的思想不难，就是有些初始化条件和边界条件写起来可能有些淡疼……
首先肯定是要先建出来虚树的……
对于第一问，开个数组$g[i]$，存$i$这个子树往下的所有路径的总长度，记录一下贡献就好了。
对于第二问和第三问，原本求这种我只会记录最长和次长然后做……这次看别的博客学习到了不用这么麻烦QAQ
我们维护一个$Min[i]$，一个$Max[i]$，分别表示这个点往下的最短/最长链。更新代码简单易懂 我也懒得说咋做了
Code
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N (1000009)
#define LL long long
using namespace std; struct Edge{int to,next;}edge[N<<];
int n,m,k,u,v,dfs_num;
int a[N],f[N][],DFN[N],Depth[N],vis[N],size[N];
LL g[N],Max[N],Min[N],ans1,ans2,ans3;
int head[N],num_edge; void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void DFS(int x,int fa)
{
f[x][]=fa;
for (int i=; i<=; ++i)
f[x][i]=f[f[x][i-]][i-];
DFN[x]=++dfs_num; Depth[x]=Depth[fa]+;
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].to!=fa) DFS(edge[i].to,x);
} int LCA(int x,int y)
{
if (Depth[x]<Depth[y]) swap(x,y);
for (int i=; i>=; --i)
if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];
if (x==y) return x;
for (int i=; i>=; --i)
if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
return f[x][];
} struct E{int to,next,len;}EDGE[N<<];
int HEAD[N],NUM_EDGE;
int stack[N],top;
bool cmp(int x,int y) {return DFN[x]<DFN[y];} void ADD(int u,int v)
{
if (u==v) return;//因为我的写法问题所以这里记得特判！
EDGE[++NUM_EDGE].to=v;
EDGE[NUM_EDGE].next=HEAD[u];
EDGE[NUM_EDGE].len=Depth[v]-Depth[u];
HEAD[u]=NUM_EDGE;
} void Insert(int x)
{
if (top==) {stack[++top]=x; return;}
int lca=LCA(x,stack[top]);
if (lca==stack[top]) {stack[++top]=x; return;}
while (top> && DFN[stack[top-]]>=DFN[lca])
ADD(stack[top-],stack[top]), top--;
if (lca!=stack[top]) ADD(lca,stack[top]), stack[top]=lca;
stack[++top]=x;
} void Build()
{
stack[top=]=;
for (int i=; i<=k; ++i) Insert(a[i]);
while (top>=) ADD(stack[top-],stack[top]), top--;
} void DP(int x)
{
size[x]=vis[x]; g[x]=;
Min[x]=vis[x]?:2e9;
Max[x]=vis[x]?:-2e9;
for (int i=HEAD[x]; i; i=EDGE[i].next)
{
int y=EDGE[i].to;
DP(y);
ans1+=(LL)size[x]*size[y]*EDGE[i].len+g[x]*size[y]+g[y]*size[x];
size[x]+=size[y];
g[x]+=g[y]+(LL)EDGE[i].len*size[y];
ans2=min(ans2,Min[x]+Min[y]+EDGE[i].len);
ans3=max(ans3,Max[x]+Max[y]+EDGE[i].len);
Min[x]=min(Min[x],Min[y]+EDGE[i].len);
Max[x]=max(Max[x],Max[y]+EDGE[i].len);
}
HEAD[x]=;
} int main()
{
scanf("%d",&n);
for (int i=; i<=n-; ++i)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
DFS(,);
scanf("%d",&m);
for (int i=; i<=m; ++i)
{
scanf("%d",&k);
for (int j=; j<=k; ++j)
scanf("%d",&a[j]), vis[a[j]]=;
sort(a+,a+k+,cmp);
NUM_EDGE=; ans1=; ans2=2e9; ans3=-2e9;
Build(); DP();
printf("%lld %lld %lld\n",ans1,ans2,ans3);
for (int j=; j<=k; ++j) vis[a[j]]=;
}
}