题目：

考场上想到了一个子树里如果有多个 “段” 准备和其他位置的 “段” 拼在一起，那么这个子树里的这些 “段” 一定两两间互相有父子关系。

准备设计一个 DP ，但觉得很难弄。比如很难存下状态，因为还要存 “有几个待合并的“段”” 、“那些“段”的最大值是什么” 之类的。所以就只写了 60 分。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}ll Mx(ll a,ll b){
     return a>b?a:b;}ll Mn(ll a,ll b){
     return a
         
          =dfn[y]&&dfn[x]<=ot[y])||(dfn[y]>=dfn[x]&&dfn[y]<=ot[x]);}  void solve()  {    ini_dfs(1); bin[0]=1;    for(int i=1;i<=n;i++)bin[i]=bin[i-1]<<1;    for(int s=0;s
          
           v;}  void dfsa(int cr,int fa)  {    a[++ta]=c[cr];    for(int i=hd[cr],v;i;i=nxt[i])      if((v=to[i])!=fa) dfsa(v,cr);  }  void dfsb(int cr,int fa)  {    b[++tb]=c[cr];    for(int i=hd[cr],v;i;i=nxt[i])      if((v=to[i])!=fa) dfsb(v,cr);  }  void solve()  {    if(cd[1]==1)      {    for(int i=1;i<=n;i++)ans+=c[i];    printf("%lld\n",ans); return;      }    dfsa(to[hd[1]],1); dfsb(to[nxt[hd[1]]],1);    sort(a+1,a+ta+1,cmp); sort(b+1,b+tb+1,cmp);    for(int i=1,lm=Mn(ta,tb);i<=lm;i++)      ans+=Mx(a[i],b[i]);    if(ta
           
            1){fg=1;break;} if(!fg&&cd[1]<=2){S2::solve();return 0;} return 0;}
           
          
         
        
       
      

其实从 “链” 的部分受到启发，如果两个部分互相没有父子关系，就是把最大值和最大值放在一段，次大值和次大值放在一段这样贪心。

那么在树上也可以贪心（而不是 DP ），不用管 “有几个待合并的段” ，直接把子树里的所有已有的 “段” 都视作待合并的，那么就用大根堆维护子树里的 “段”。在 dfs 树的时候，合并两个子树就用堆的启发式合并即可。

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
   if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}int Mx(int a,int b){
   return a>b?a:b;}int Mn(int a,int b){
   return a
         

q[N];void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}void dfs(int cr){ for(int i=hd[cr],v;i;i=nxt[i]) { dfs(v=to[i]); if(q[rt[cr]].size()