Codeforces 739B(树上路径倍增及差分)

143 阅读 0 评论 95 点赞

我是靠谱客的博主感动便当，这篇文章主要介绍Codeforces 739B(树上路径倍增及差分)，现在分享给大家，希望可以做个参考。

比较考验我思维的一道好题。

首先，做一遍DFS预处理出t[i][j]和d[i][j]。t[i][j]表示从第i个节点到离他第2^j近的祖先，d[i][j]表示从i开始到t[i][j]的路径上的路径权值总和。

在第一次DFS的同时，对节点x进行定位(结果为dist(x, y)<=a(y))的离x最远的x的某个祖先，然后进行O(1)的差分。

第一次DFS完成后，做第二次DFS统计答案(统计差分后的结果)。时间复杂度为O(NlgN)

代码送上。

复制代码

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)                for(int i(0); i <  (n); ++i)
#define rep(i,a,b)              for(int i(a); i <= (b); ++i)
#define dec(i,a,b)              for(int i(a); i >= (b); --i)
#define for_edge(i,x)           for(int i = H[x]; i; i = X[i])

#define LL      long long
#define ULL     unsigned long long
#define MP      make_pair
#define PB      push_back
#define FI      first
#define SE      second
#define INF     1 << 30
#define sz(x)	(int)x.size()

const int N     =    200000      +       10;
const int M     =    10000       +       10;
const int Q     =    1000        +       10;
const int A     =    30          +       1;

vector <int> v[N], c[N];
LL a[N], deep[N];
LL x, y;
int n, cnt;
LL t[N][A], d[N][A];
LL g[N], value[N];
LL s[N];
LL ans[N];

void dfs(int x, int fa){
	if (g[x]){
		t[x][0] = g[x];
		d[x][0] = value[x];
		for (int i = 0; t[t[x][i]][i]; ++i){
			t[x][i + 1] = t[t[x][i]][i];
			d[x][i + 1] = d[t[x][i]][i] + d[x][i];
		}
		int now = x, noww = 0;
		bool flag = false;
		dec(i, 20, 0){
			if (t[now][i] && d[now][i] + noww <= a[x]){
				noww += d[now][i];
				now = t[now][i];
				flag = true;
			}
		}
		if (flag){
			--s[g[now]]; ++s[g[x]];
		}
	}

REP(i, sz(v[x])){
		int u = v[x][i];
		deep[u] = deep[x] + 1;
		dfs(u, x);
	}
}

void dfs2(int x){
	ans[x] += s[x];
	REP(i, sz(v[x])){
		dfs2(v[x][i]);
		ans[x] += ans[v[x][i]];
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.txt", "r", stdin);
	freopen("test.out", "w", stdout);
#endif

scanf("%d", &n);
	rep(i, 1, n) scanf("%lld", a + i);
	rep(i, 2, n){
		scanf("%lld%lld", &x, &y); g[i] = x; value[i] = y;
		v[x].PB(i), c[x].PB(y);
	}

memset(s, 0, sizeof s);
	cnt = 0;
	deep[1] = 0;
	dfs(1, 0);
	memset(ans, 0, sizeof ans);
	dfs2(1);
	rep(i, 1, n - 1) printf("%lld ", ans[i]);
	printf("%lldn", ans[n]);

return 0;

}

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)                for(int i(0); i <  (n); ++i)
#define rep(i,a,b)              for(int i(a); i <= (b); ++i)
#define dec(i,a,b)              for(int i(a); i >= (b); --i)
#define for_edge(i,x)           for(int i = H[x]; i; i = X[i])

#define LL      long long
#define ULL     unsigned long long
#define MP      make_pair
#define PB      push_back
#define FI      first
#define SE      second
#define INF     1 << 30
#define sz(x)	(int)x.size()

const int N     =    200000      +       10;
const int M     =    10000       +       10;
const int Q     =    1000        +       10;
const int A     =    30          +       1;


vector <int> v[N], c[N];
LL a[N], deep[N];
LL x, y;
int n, cnt;
LL t[N][A], d[N][A];
LL g[N], value[N];
LL s[N];
LL ans[N];

void dfs(int x, int fa){
	if (g[x]){
		t[x][0] = g[x];
		d[x][0] = value[x];
		for (int i = 0; t[t[x][i]][i]; ++i){
			t[x][i + 1] = t[t[x][i]][i];
			d[x][i + 1] = d[t[x][i]][i] + d[x][i];
		}
		int now = x, noww = 0;
		bool flag = false;
		dec(i, 20, 0){
			if (t[now][i] && d[now][i] + noww <= a[x]){
				noww += d[now][i];
				now = t[now][i];
				flag = true;
			}
		}
		if (flag){
			--s[g[now]]; ++s[g[x]];
		}
	}

	REP(i, sz(v[x])){
		int u = v[x][i];
		deep[u] = deep[x] + 1;
		dfs(u, x);
	}
}

void dfs2(int x){
	ans[x] += s[x];
	REP(i, sz(v[x])){
		dfs2(v[x][i]);
		ans[x] += ans[v[x][i]];
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.txt", "r", stdin);
	freopen("test.out", "w", stdout);
#endif

	scanf("%d", &n);
	rep(i, 1, n) scanf("%lld", a + i);
	rep(i, 2, n){
		scanf("%lld%lld", &x, &y); g[i] = x; value[i] = y;
		v[x].PB(i), c[x].PB(y);
	}

	memset(s, 0, sizeof s);
	cnt = 0;
	deep[1] = 0;
	dfs(1, 0);
	memset(ans, 0, sizeof ans);
	dfs2(1);
	rep(i, 1, n - 1) printf("%lld ", ans[i]);
	printf("%lldn", ans[n]);

	return 0;

}