0pts 全RE 求条 悬关
查看原帖
0pts 全RE 求条 悬关
403813
HirasawaYuii楼主2025/1/15 19:01
// Problem: P3833 [SHOI2012] 魔法树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3833
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2025-01-15 14:56:33
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mst(x, y) memset(x, y, sizeof(x))
#define pii pair<ll, ll>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

ll read(){ll x = 0, f = 1;char c = getchar();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9'){x = 10*x+c-'0';c = getchar();}return f*x;}
void writ(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) writ(x/10);putchar(x%10 | 0x30);return;}
void write(ll x){writ(x);puts("");}
void wr(ll x){writ(x);putchar(' ');}
const ll N = 400005, inf = 0x3f3f3f3f;

ll n, m, idx;
ll hd[N], ver[N], nxt[N], fa[N], son[N], top[N], rev[N], seg[N], siz[N], dep[N];	
struct SegmentTree{
	ll l, r, sum, lazy;
	ll len(){
		return r-l+1;
	}
}t[4*N];

void adde(ll x, ll y){
	nxt[++idx] = hd[x];
	ver[idx] = y;
	hd[x] = idx;
}
void dfs1(ll x, ll pre){
	fa[x] = pre, dep[x] = dep[pre]+1, siz[x] = 1;
	ll maxn = -inf;
	for(ll i = hd[x];i;i = nxt[i]){
		ll y = ver[i];
		if(y == pre) continue;
		dfs1(y, x);
		if(siz[y] > maxn) son[x] = y, maxn = siz[y];
		siz[x] += siz[y];
	}
}
void dfs2(ll x, ll pre){
	if(son[x]){
		seg[son[x]] = ++idx;
		rev[idx] = son[x];
		top[son[x]] = top[x];
		dfs2(son[x], x);
	}
	for(ll i = hd[x];i;i = nxt[i]){
		ll y = ver[i];
		if(y == pre || y == son[x]) continue;
		seg[y] = ++idx, rev[idx] = y, top[y] = y;
		dfs2(y, x);
	}
}
void build(ll p, ll l, ll r){
	t[p].l = l, t[p].r = r;
	if(l == r) return;
	ll mid = (l+r)>>1;
	build(p*2, l, mid);
	build(p*2+1, mid+1, r);
}
void pushup(ll p){t[p].sum = t[p*2].sum+t[p*2+1].sum;}
void pushdown(ll p){
	if(!t[p].lazy) return;
	t[p*2].sum += t[p].lazy*t[p*2].len();
	t[p*2].lazy += t[p].lazy;
	t[p*2+1].sum += t[p].lazy*t[p*2+1].len();
	t[p*2+1].lazy += t[p].lazy;
	t[p].lazy = 0;
}
void add(ll p, ll l, ll r, ll v){
	if(l <= t[p].l && t[p].r <= r){
		t[p].lazy += v;
		t[p].sum += v*t[p].len();
		return;
	}
	ll mid = (t[p].l+t[p].r)>>1;
	pushdown(p);
	if(l <= mid) add(p*2, l, r, v);
	if(mid <= r) add(p*2+1, l, r, v);
	pushup(p);
}
void change(ll x, ll y, ll v){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		add(1, seg[top[x]], seg[x], v);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	add(1, seg[x], seg[y], v);
}
ll ask(ll p, ll l, ll r){
	if(l <= t[p].l && t[p].r <= r){
		return t[p].sum;
	}
	ll mid = (t[p].l+t[p].r)>>1, res = 0;
	pushdown(p);
	if(l <= mid) res += ask(p*2, l, r);
	if(mid <= r) res += ask(p*2+1, l, r);
	return res;
}
void init(){
	n = read();
	for(ll i = 1;i < n;i++){
		int x, y;
		cin >> x >> y;
		x++, y++;
		adde(x, y);adde(y, x);
	}
	dfs1(1, 0);
	idx = 1, seg[1] = 1, rev[1] = 1, top[1] = 1;
	dfs2(1, 0);
	build(1, 1, n);
}
void solve(){
	m = read();
	while(m--){
		char c;ll x, y, v;
		cin >> c >> x;x++;
		if(c == 'A'){
			cin >> y >> v;
			y++;
			change(x, y, v);
		}
		else cout << ask(1, seg[x], seg[x]+siz[x]-1) << endl;
	}
}
	
signed main(){
	init();
	solve();
	return 0; 
}
2025/1/15 19:01
加载中...