过样例了WA求调,悬赏一关注
查看原帖
过样例了WA求调,悬赏一关注
539211
lzyqwq楼主2022/11/9 19:12
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define co const
#define il inline
co int N = 1e5 + 5;
int n, q, f[N], t[N], d[N], st[N], ed[N], dfn[N], sum[N << 2], sz[N], h[N], cnt, add[N << 2];
vector<int> g[N];
il void dfs1(co int &x, co int &fa) {
	sz[x] = 1;
	for (co int &i : g[x]) {
		if (i ^ fa) {
			d[i] = d[f[i] = x] + 1;
			dfs1(i, x);
			sz[x] += sz[i];
		}
	}
}
il void dfs2(co int &x, co int &fa) {
	for (co int &i : g[x]) {
		if (i ^ fa) {
			if (sz[i] << 1 > sz[x]) {
				t[h[x] = i] = t[x];
			} else {
				t[i] = i;
			}
			dfs2(i, x);
		}
	}
}
il void dfs3(co int &x, co int &fa) {
	dfn[x] = st[x] = ++cnt;
	if (h[x]) {
		dfs3(h[x], x);
	}
	for (co int &i : g[x]) {
		if (i ^ fa && i ^ h[x]) {
			dfs3(i, x);
		}
	}
	ed[x] = cnt;
}
il void pushdown(co int &x, co int &l, co int &r) {
    co int &mid = l + r >> 1;
	sum[x << 1] += (mid - l + 1) * add[x];
	sum[x << 1 | 1] += (r - mid) * add[x];
	add[x << 1] += add[x];
	add[x << 1 | 1] += add[x];
	add[x] = 0;
}
il int query(co int &x, co int &l, co int &r, co int &ql, co int &qr) {
	if (ql <= l && qr >= r) {
		return sum[x];
	}
	pushdown(x, l, r);
	co int &mid = l + r >> 1;
	int s = 0;
	if (ql <= mid) {
		s += query(x << 1, l, mid, ql, qr);
	}
	if (qr > mid) {
		s += query(x << 1 | 1, mid + 1, r, ql, qr);
	}
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
	return s;
}
il void change(co int &x, co int &l, co int &r, co int &ql, co int &qr, co int &v) {
	if (ql <= l && qr >= r) {
		sum[x] += (r - l + 1) * (add[x] = v);
		return;
	}
	pushdown(x, l, r);
	co int &mid = l + r >> 1;
	if (ql <= mid) {
		change(x << 1, l, mid, ql, qr, v);
	}
	if (qr > mid) {
		change(x << 1 | 1, mid + 1, r, ql, qr, v);
	}
	sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
il void modify(int x, int y, int v) {
	while (t[x] ^ t[y]) {
		if (d[t[x]] < d[t[y]]) {
			swap(x, y);
		}
		change(1, 1, n, dfn[t[x]], dfn[x], v);
		x = f[t[x]];
	}
	if (d[x] > d[y]) {
		swap(x, y);
	}
	change(1, 1, n, dfn[x], dfn[y], v);
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin >> n;
	for (re int i = 1, u, v; i ^ n; ++i) {
		cin >> u >> v;
		++u;
		++v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	dfs1(1, 0);
	dfs2(t[1] = 1, 0);
	dfs3(1, 0);
	cin >> q;
	for (re int u, v, d; q--; ) {
		char c;
		cin >> c >> u;
		++u;
		if (c ^ 'Q') {
			cin >> v >> d;
			++v;
			modify(u, v, d);
		} else {
			cout << query(1, 1, n, st[u], ed[u]) << '\n';
		}
	}
}
2022/11/9 19:12
加载中...