男神的树

题目链接：http://acm.xidian.edu.cn/problem.php?id=1164

DFS

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

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

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

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

代码如下：

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<vector>
 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<n-1;++i){
27         scanf("%d%d",&u,&v);
28         father[v]=u;
29     }
30     for(int i=1;i<=n;++i)
31         scanf("%d",&value[i]);
32     for(int i=1;i<=n;++i)
33         sum+=dfs(i);
34     printf("%lld
",sum);
35 }