题目大意：

　　有一棵n个结点的树，请你搞一些破坏。

　　直接暴力破坏一个结点i的代价为p[i]。

　　当然还有非暴力破坏的方法。

　　每个结点i有一个防御上限c[i]，如果与这个点直接相连的点中已经有c[i]个被破坏，那么这个点就会自己坏掉。

　　一个点坏掉以后要过一秒钟才会带坏周围的点。

　　如果不考虑时间问题，如何用最小的代价把整棵树搞坏？

思路：

　　树形DP。

　　然而这题并没有明显的上下级关系，也就是说父结点和子结点会互相影响。

　　考虑同时做两个DP，f和g。

　　f[i]表示先搞坏i子树再搞坏母树的最小代价。

　　g[i]表示先搞坏母树再搞坏i子树的最小代价。

　　显然对于一个点，不仅有f和g的情况，还分为手动破坏和自动破坏两种情况。

　　我们不妨先考虑手动搞坏i点的情况，也就是说，令f[i]=g[i]=p[i]+sum{g[j]|j in son[i]}。

　　如果要自动搞坏i点，也就是说要把其中c[i]个g[j]替换成对应的f[j]，可以对子结点按照f[j]-g[j]排序。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 typedef long long int64; 6 const int64 inf=0x7fffffffffffffffll; 7 inline int getint() { 8     register char ch; 9     while(!isdigit(ch=getchar()));10     register int x=ch^'0';11     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');12     return x; 13 }14 const int N=50001;15 std::vector
         
           e[N];16 inline void add_edge(const int &u,const int &v) {17     e[u].push_back(v);18     e[v].push_back(u);19 }20 inline void init() {21     for(register int i=1;i
          

::iterator i=e[x].begin();i