XDU 1164

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]; //clear the initial point
return abs(sum[i]);
}
ll x = 0;
A[i] += sum[fa[i]]; //clear the tag of this point
x += abs(A[i]);
sum[i] += sum[fa[i]] - A[i]; //clear the tag of now
return x;
}
int main()
{
ll ans = 0;
// scanf("%d", &n);
scan_d(n);
fa[1] = 0;
for(register int i = 1, u, v; i < n; ++ i)
{
//scanf("%d %d", &u, &v);
scan_d(u);
scan_d(v);
fa[v] = u;
}
for(register int i = 1; i <= n; ++ i) scan_d(A[i]); //scanf("%d", A + i);
for(register int i = 1; i <= n; ++ i) ans += dfs(i);
printf("%lld\n", ans);
return 0;
}
文章目录
  1. 1. XDOJ 1164 男神的树
    1. 1.1. 题目描述
    2. 1.2. 题解
    3. 1.3. AC Code
{{ live2d() }}