OI

BZOJ 1984: 月下“毛景树”

 Description

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。

 Change k w：将第k条树枝上毛毛果的个数改变为w个。  Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。  Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。

 Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数N。 接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。

Output

对于毛毛虫的每个询问操作，输出一个答案。

Sample Input

4

1 2 8

1 3 7

3 4 9

Max 2 4

Cover 2 4 5

Add 1 4 10

Change 1 16

Max 2 4

Stop

Sample Output

9

16

【Data Range】

1<=N<=100,000，操作+询问数目不超过100,000。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

Solution

SB题，调了一晚上QAQ。“都快憋出内伤了！”

我的大好青春啊。。。本来想今晚上看看拉格朗日和后缀数组的，一道题调了一晚上。怎么混SDOI2016啊…

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
 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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int INF = 1<<30;
typedef long long LL;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
char str[10];
const int maxn = 100009;

int siz[maxn], top[maxn], dep[maxn], son[maxn], fa[maxn], tid[maxn], dfs_clock = 0, soncost[maxn];
int mx[maxn<<2], lazy[maxn<<2], cov[maxn<<2];

struct edge_type {
	int to, next, w;
} edge[maxn<<1];
int h[maxn], cnte = 0;
void ins(int u, int v, int w) {
	edge[++cnte].to = v;
	edge[cnte].next = h[u];
	edge[cnte].w = w;
	h[u] = cnte;
}

int A[maxn];
int dfs1(int now, int father, int deep) {
	dep[now] = deep; fa[now] = father; son[now] = 0; siz[now] = 1;
	for (int i = h[now]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == father) continue;
		siz[now] += dfs1(v, now, deep+1);
		if (siz[v] > siz[son[now]]) {
			son[now] = v;
			soncost[now] = edge[i].w;
		}
	}
	return siz[now];
}
void dfs2(int now, int father, int tp, int cost) {
	top[now] = tp; tid[now] = ++dfs_clock; A[dfs_clock] = cost;
	if (son[now]) {
		dfs2(son[now], now, tp, soncost[now]);
		for (int i = h[now]; i; i = edge[i].next) {
			int v = edge[i].to;
			if (v == father || v == son[now]) continue;
			dfs2(v, now, v, edge[i].w);
		}
	}
}

void pd(int x) {
	int l = x << 1, r = l | 1;
	if (cov[x] != -1) {
		cov[l] = cov[r] = cov[x];
		lazy[l] = lazy[r] = 0;
		mx[l] = mx[r] = cov[x];
		cov[x] = -1;
	}
	if (lazy[x]) {
		mx[l] += lazy[x];
		mx[r] += lazy[x];
		lazy[l] += lazy[x];
		lazy[r] += lazy[x];
		lazy[x] = 0;
	}
}
void pu(int x) {
	mx[x] = max(mx[x<<1], mx[x<<1|1]);
}
int build(int now, int l, int r) {
	cov[now] = -1;
	if (l == r) return mx[now] = A[l];
	int mid = (l + r) >> 1;
	return mx[now] = max(build(now<<1, l, mid), build(now<<1|1, mid+1, r));
}
int query(int now, int l, int r, int ll, int rr) {
	if (ll <= l && r <= rr) return mx[now];
	pd(now);
	int mid = (l + r) >> 1, ret = -INF;
	if (ll <= mid) ret = query(now<<1, l, mid, ll, rr);
	if (rr > mid) ret = max(ret, query(now<<1|1, mid+1, r, ll, rr));
	return ret;
}
void change(int now, int l, int r, int ll, int rr, int val) {
	if (ll <= l && r <= rr) {
		mx[now] += val;
		lazy[now] += val;
		return;
	}
	pd(now);
	int mid = (l + r) >> 1;
	if (ll <= mid) change(now<<1, l, mid, ll, rr, val);
	if (rr > mid) change(now<<1|1, mid+1, r, ll, rr, val);
	pu(now);
}
void change1(int now, int l, int r, int ll, int rr, int val) {
	if (ll <= l && r <= rr) {
		mx[now] = val;
		lazy[now] = 0;
		cov[now] = val;
		return;
	}
	pd(now);
	int mid = (l + r) >> 1;
	if (ll <= mid) change1(now<<1, l, mid, ll, rr, val);
	if (rr > mid) change1(now<<1|1, mid+1, r, ll, rr, val);
	pu(now);
}

int n, ex[maxn], ey[maxn];
int ask(int x, int y) {
	if (x == y) return 0;
	int ret = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = max(ret, query(1, 1, n, tid[top[x]], tid[x]));
		x = fa[top[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	if (x != y) ret = max(ret, query(1, 1, n, tid[y]+1, tid[x]));
	return ret;
}
void add(int x, int y, int z) {
	if (x == y) return;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		change(1, 1, n, tid[top[x]], tid[x], z);
		x = fa[top[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	if (x != y) change(1, 1, n, tid[y]+1, tid[x], z);
}
void chan(int x, int z) {
	int y;
	if (dep[ex[x]] > dep[ey[x]]) y = ex[x];
	else y = ey[x];
	change1(1, 1, n, tid[y], tid[y], z);
}
void cover(int x, int y, int z) {
	if (x == y) return;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		change1(1, 1, n, tid[top[x]], tid[x], z);
		x = fa[top[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	if (x != y) change1(1, 1, n, tid[y]+1, tid[x], z);
}
int main() {/*
	freopen("je.out", "w", stdout);
	freopen("je.in", "r", stdin);*/
	n = getint(); int x, y, z;
	for (int i = 1; i < n; ++i) {
		x = getint(); y = getint(); z = getint();
		ex[i] = x;
		ey[i] = y;
		ins(x, y, z);
		ins(y, x, z);
	}
	dfs1(1, 0, 1);
	dfs2(1, 0, 1, 0);
	build(1, 1, n);
	while(true) {
		scanf("%s", str);
		if (str[1] == 't') break;
		if (str[1] == 'a') {
			x = getint(); y = getint();
			printf("%d\n", ask(x, y));
		}
		if (str[1] == 'd') {
			x = getint(); y = getint(); z = getint();
			add(x, y, z);
		}
		if (str[1] == 'h') {
			x = getint(); z = getint();
			chan(x, z);
		}
		if (str[1] == 'o') {
			x = getint(); y = getint(); z = getint();
			cover(x, y, z);
		}
	}
	return 0;
}