要自下向上调整，尽可能用一个道具修改多个；

搜的时候记录叶节点的最大深度，减一下就好了。

#include
     
      #include
      
       #include
       
        #define R register intusing namespace std;struct edge {    int v,w,nxt;}e[1000010];int n,cnt,s;int fir[500010];long long ans,mx[500010];inline void add(int u,int v,int w) {e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=fir[u],fir[u]=cnt;}inline int g() {    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;}void dfs(int u,int fa) {    //cout<
        <<" "<
         
          <
         
       
      
     

---

 

2019.04.26