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

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

---

先吐槽一句：这个样例真良心

标记点个数与\(n\)同阶？上虚树！建出虚树后考虑求解答案，权值和二次换根即可，最大最小值在dfs的时候记录最大次大，最小次小，然后更新即可

/*program from Wolfycz*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline char gc(){    static char buf[1000000],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int frd(){    int x=0,f=1; char ch=gc();    for (;ch<'0'||ch>'9';ch=gc())   if (ch=='-')    f=-1;    for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';    return x*f;}inline int read(){    int x=0,f=1; char ch=getchar();    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<3)+(x<<1)+ch-'0';    return x*f;}inline void print(int x){    if (x<0)    putchar('-'),x=-x;    if (x>9)    print(x/10);    putchar(x%10+'0');}const int N=1e6;int ID[N+10];bool cmp(int x,int y){return ID[x]
         
          z.Mn) x.Sn=x.Mn,x.Mn=z.Mn; else if (x.Sn>z.Mn) x.Sn=z.Mn; } void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;} void insert(int x,int y,int z){join(x,y,z),join(y,x,z);} void insert(int x,int y){insert(x,y,HLD.dis(x,y));} void rebuild(int m){ int top=0; tot=0; sort(A+1,A+1+m,cmp); stack[++top]=1; for (int i=1;i<=m;i++){ int x=A[i],lca=HLD.LCA(stack[top],x); if (x==1) continue; if (lca==stack[top]){ stack[++top]=x; continue; } while (true){ int y=stack[top-1]; if (ID[y]>=ID[lca]){ insert(stack[top--],y); continue; }else{ if (lca==stack[top]) break; insert(stack[top],lca); stack[top]=lca; break; } } stack[++top]=x; } while (top>1){ insert(stack[top],stack[top-1]); top--; } } void dfs(int x,int fa){ f[x].clear(); size[x]=mark[x]; if (mark[x]) f[x].init(); for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){ if (son==fa) continue; dfs(son,x),size[x]+=size[son]; updata(f[x],f[son],val[p]); } Max=max(Max,f[x].Mx+f[x].Sx); Min=min(Min,f[x].Mn+f[x].Sn); } void sum(int x,int fa){ for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){ if (son==fa) continue; sum(son,x); Ans+=1ll*size[son]*(All-size[son])*val[p]; } now[x]=0; } void work(){ int m=read(); for (int i=1;i<=m;i++) mark[A[i]=read()]=1; rebuild(m),Max=-inf,Min=inf; dfs(1,0),All=size[1],Ans=0,sum(1,0); printf("%lld %d %d\n",Ans,Min,Max); for (int i=1;i<=m;i++) mark[A[i]]=0; }}T;int main(){ int n=read(); for (int i=1;i