백준5916 농장 관리

작성일 | In

문제 링크

  • http://icpc.me/5916

문제 출처

  • 2011 December USACO Gold 3번

사용 알고리즘

  • HLD
  • 세그 레이지

풀이

기초적인 HLD + Lazy Propagation 문제입니다.

전체 코드

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<int> inp[101010], g[101010];
int par[101010], sz[101010], dep[101010], in[101010], top[101010];
int chk[101010];
int n, q, pv;

ll tree[404040];
ll tmp[404040];

void push(int node, int s, int e){
	if(!tmp[node]) return;
	tree[node] += (e-s+1) * tmp[node];
	if(s ^ e){
		tmp[node*2] += tmp[node];
		tmp[node*2+1] += tmp[node];
	}
	tmp[node] = 0;
}

void seg_update(int node, int s, int e, int l, int r, ll v){
	push(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		tree[node] += (e-s+1) * v;
		if(s ^ e){
			tmp[node*2] += v;
			tmp[node*2+1] += v;
		}
		return;
	}
	int m = s + e >> 1;
	seg_update(node*2, s, m, l, r, v);
	seg_update(node*2+1, m+1, e, l, r, v);
	tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

ll seg_query(int node, int s, int e, int l, int r){
	push(node, s, e);
	if(r < s || e < l) return 0;
	if(l <= s && e <= r) return tree[node];
	int m = s + e >> 1;
	return seg_query(node*2, s, m, l, r) + seg_query(node*2+1, m+1, e, l, r);
}

void dfs(int v = 1){
	chk[v] = 1;
	for(auto i : inp[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		g[v].push_back(i);
		dfs(i);
	}
}

void dfs1(int v = 1){
	sz[v] = 1;
	for(auto &i : g[v]){
		par[i] = v;
		dep[i] = dep[v] + 1;
		dfs1(i);
		sz[v] += sz[i];
		if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
	}
}

void dfs2(int v = 1){
	in[v] = ++pv;
	for(auto i : g[v]){
		top[i] = i == g[v][0] ? top[v] : i;
		dfs2(i);
	}
}

void update(int a, int b, ll c){
	while(top[a] != top[b]){
		if(dep[top[a]] < dep[top[b]]) swap(a, b);
		int st = top[a];
		seg_update(1, 1, n, in[st], in[a], c);
		a = par[st];
	}
	if(in[a] > in[b]) swap(a, b);
	seg_update(1, 1, n, in[a]+1, in[b], c);
}

ll query(int a, int b){
	ll ret = 0;
	while(top[a] != top[b]){
		if(dep[top[a]] < dep[top[b]]) swap(a, b);
		int st = top[a];
		ret += seg_query(1, 1, n, in[st], in[a]);
		a = par[st];
	}
	if(in[a] > in[b]) swap(a, b);
	ret += seg_query(1, 1, n, in[a]+1, in[b]);
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for(int i=1; i<n; i++){
		int s, e; cin >> s >> e;
		inp[s].push_back(e);
		inp[e].push_back(s);
	}
	dfs(); dfs1(); dfs2();
	while(q--){
		char op; int a, b;
		cin >> op >> a >> b;
		if(op == 'P'){
			update(a, b, 1);
		}else{
			cout <<query(a, b) << "\n";
		}
	}
}