Description

 

Input

Output

 

Sample Input

2 3 1 0 1 2 2 1 0 1 2 0 2 1 4 0 1 2 0 3 0 1 3 0 1 0 1

Sample Output

1.0000 5.0000 
       <空行>
         11.0000
       

 

Data Constraint

分析

 

//                  赤い面 //                 赤い仮面 //                白 色围 巾 //              手 强化筋肉 手 //             手  强化筋肉   手 //           手    强化筋肉    手 //                 双重飓风//山               腿    腿 //山山            腿      腿 //山山           腿        腿 //山山山       脚          脚 //山山山山管钢管钢管钢管钢管钢管钢管钢管钢管 //             你妈的，为甚麽 #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=5e4+10;struct Edge {    int u,v,nx;}g[2*N];int cnt,list[N];int T,n,q;int f1[N],f2[N],deg[N],d[N],f[N][20];void Add(int u,int v) {g[++cnt]=(Edge){u,v,list[u]};list[u]=cnt;deg[u]++;}void DFS1(int u,int fa) {    f1[u]=deg[u];    for (int i=list[u];i;i=g[i].nx)        if (g[i].v!=fa) DFS1(g[i].v,u),f1[u]+=f1[g[i].v];}void DFS2(int u,int fa) {    int sum=deg[u];    for (int i=list[u];i;i=g[i].nx)        if (g[i].v!=fa) sum+=f1[g[i].v];        else sum+=f2[u];    for (int i=list[u];i;i=g[i].nx)        if (g[i].v!=fa) f2[g[i].v]=sum-f1[g[i].v],DFS2(g[i].v,u);}void Build(int u,int fa) {    d[u]=d[fa]+1;f[u][0]=fa;    f1[u]+=f1[fa];f2[u]+=f2[fa];    for (int i=list[u];i;i=g[i].nx) if (g[i].v!=fa) Build(g[i].v,u);}int Get_LCA(int a,int b) {    if (d[a]
         
          =0;i--) if (d[f[a][i]]>=d[b]) a=f[a][i];    if (a==b) return a;    for (int i=19;i>=0;i--) if (f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];    return f[a][0];}int main() {    for (scanf("%d",&T);T;T--) {        scanf("%d",&n);cnt=0;        memset(list,0,sizeof list);        memset(f1,0,sizeof f1);        memset(f2,0,sizeof f2);        memset(f,0,sizeof f);        memset(d,0,sizeof d);        memset(deg,0,sizeof deg);        for (int i=1,u,v;i