男神的树

题目链接：

DFS

早上才写了一题...回来发现除了这题外其他都好简单= =

这题用vector存孩子会爆空间，所以想到用father[N]存父节点，lazy[N]数组存修改值（和线段树的lazy用法一样），vis[N]标记是否被dfs，再用dfs向上搞

//其实数据比较弱1e6就可以过，lazy没用LL好像也没问题，后来改了发1e6的，没改名次(╯‵□′)╯︵┻━┻耗时更长了什么鬼...

//这样做内存消耗125M，差不多要挂了= =

代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N (int)(1e7+5) 5 using namespace std; 6 typedef long long LL; 7 int father[N],value[N],lazy[N]; 8 bool vis[N]; 9 int n,u,v;10 LL sum;11 LL dfs(int index){12     if(vis[index])return 0;13     vis[index]=1;14     if(father[index]==0){15         lazy[index]-=value[index];16         return abs(lazy[index]);17     }18     LL s=dfs(father[index]);19     value[index]+=lazy[father[index]];20     lazy[index]+=(lazy[father[index]]-value[index]);21     s+=abs(value[index]);22     return s;23 }24 int main(void){25     scanf("%d",&n);26     for(int i=0;i