22
XDOJ 1164 男神的树
题目描述
给你一棵树,每次操作可以选择一个节点,然后给以这个节点为根的子树上的所有节点的权值加一或者减一。
最少需要多少次操作才可以把树上的权值全部变成 0 。$n \leq 10^7$
题解
贪心地删除每个点的值:在清除点 $x$ 的值时候,需要继承父亲的值 $fa_x$ ,然后删除自己的点的大小 $A_x$ ,将要被删除的值改为 $fa_x - A_x$ ,对于剩下的点执行同样的过程即可。
AC Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #define Linux_System #include <bits/stdc++.h> # ifdef Linux_System # define getchar getchar_unlocked # define putchar putchar_unlocked # endif using namespace std; const int maxn = 10000009; template <class T> inline bool scan_d(T & ret) { char c; int sgn; if(c = getchar(), c == EOF)return false; while(c != '-' && (c < '0' || c > '9'))c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while(c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return true; } template <class T> inline void out_number(T x) { if(x < 0) { putchar('-'); out_number(- x); return ; } if(x > 9)out_number(x / 10); putchar(x % 10 + '0'); } int n, m; int A[maxn], fa[maxn], sum[maxn]; ll dfs(int i) { if(! fa[i]) { sum[i] -= A[i]; return abs(sum[i]); } ll x = 0; A[i] += sum[fa[i]]; x += abs(A[i]); sum[i] += sum[fa[i]] - A[i]; return x; } int main() { ll ans = 0; scan_d(n); fa[1] = 0; for(register int i = 1, u, v; i < n; ++ i) { scan_d(u); scan_d(v); fa[v] = u; } for(register int i = 1; i <= n; ++ i) scan_d(A[i]); for(register int i = 1; i <= n; ++ i) ans += dfs(i); printf("%lld\n", ans); return 0; }
|