虚树，跪，貌似搞出虚树之后的DP挺好想的，然而蒟蒻还是虚的扒了题解，，

1 #include 
     
        2 #define LL long long  3 #define inf 0x3f3f3f3f  4 using namespace std;  5 inline int ra()  6 {  7     int x=0,f=1; char ch=getchar();  8     while (ch<'0' || ch>'9') {
   if (ch=='-') f=-1; ch=getchar();}  9     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 10     return x*f; 11 } 12 LL tot; 13 int bin[20]; 14 int n,K,top,cnt,q,ind,ans1,ans2; 15 int head[1000005],rehead[1000005],v[1000005]; 16 int mx[1000005],mn[1000005]; 17 int fa[1000005][20],deep[1000005],dfn[1000005],st[1000005],h[1000005]; 18 LL size[1000005],f[1000005]; 19 struct edge{ 20     int to,next,v; 21 }e[2000005],re[2000005]; 22 void insert2(int x, int y) 23 { 24     if (x==y) return; 25     re[++cnt].next=rehead[x]; re[cnt].to=y; rehead[x]=cnt; re[cnt].v=deep[y]-deep[x]; 26 } 27 void insert(int x, int y){e[++cnt].next=head[x]; e[cnt].to=y; head[x]=cnt;} 28 void pre_dfs(int x) 29 { 30     dfn[x]=++ind; 31     for (int i=1; bin[i]<=deep[x]; i++) 32             fa[x][i]=fa[fa[x][i-1]][i-1]; 33     for (int i=head[x];i;i=e[i].next) 34     { 35         if (e[i].to==fa[x][0]) continue; 36         deep[e[i].to]=deep[x]+1; 37         fa[e[i].to][0]=x; 38         size[x]+=size[e[i].to]; 39         pre_dfs(e[i].to); 40     } 41 } 42 int lca(int x, int y) 43 { 44     if (deep[x]
      
       =0; i--) 49         if (fa[x][i]!=fa[y][i]) 50             x=fa[x][i],y=fa[y][i]; 51     return x==y?x:fa[x][0]; 52 } 53 bool cmp(int a, int b){
   return dfn[a]