// ybmj #include<bits/stdc++.h> usingnamespacestd; #define lson (rt << 1) #define rson (rt << 1 | 1) #define lson_len (len - (len >> 1)) #define rson_len (len >> 1) #define pb(x) push_back(x) #define clr(a, x) memset(a, x, sizeof(a)) #define mp(x, y) make_pair(x, y) typedeflonglong ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; constint INF = 0x3f3f3f3f; constint NINF = 0xc0c0c0c0; constint maxn = 5e4+5; int a[maxn]; structHLD { int n, dfn; int sz[maxn], top[maxn], son[maxn], dep[maxn], par[maxn], id[maxn], rk[maxn]; vector<int> G[maxn]; voidinit(int n){ this->n = n; clr(son, -1); clr(diff, 0); dfn = 0; for (int i = 0; i <= n; i++) G[i].clear(); } voidaddedge(int u, int v){ G[u].pb(v); G[v].pb(u); } voiddfs(int u, int fa, int d){ dep[u] = d; par[u] = fa; sz[u] = 1; for (auto &v : G[u]) { if (v == fa) continue; dfs(v, u, d + 1); sz[u] += sz[v]; if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v; } } voidlink(int u, int t){ top[u] = t; id[u] = ++dfn; rk[dfn] = u; if (son[u] == -1) return; link(son[u], t); for (auto &v : G[u]) { if (v != son[u] && v != par[u]) link(v, v); } } voidupdate_path(int u, int v, int val){ while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); update(id[top[u]], id[u], val); u = par[top[u]]; } if (dep[u] > dep[v]) swap(u, v); update(id[u], id[v], val); }
int diff[maxn];
intlowb(int x){ return x & (-x); } intquery(int x){ int ret = 0; for (int i = x; i > 0; i -= lowb(i)) { ret += diff[i]; continue; } return ret; } voidupdate(int l, int r, int val){ for (int i = l; i <= n; i += lowb(i)) diff[i] += val; for (int i = r + 1; i <= n; i += lowb(i)) diff[i] -= val; } }; HLD hld;
intmain(){ // /* #ifndef ONLINE_JUDGE freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif // */ std::ios::sync_with_stdio(false); int n, m, q; while (cin >> n >> m >> q) { hld.init(n + 5); for (int i = 1; i <= n; i++) cin >> a[i]; int u, v, w; for (int i = 0; i < m; i++) { cin >> u >> v; hld.addedge(u, v); } hld.dfs(1, 1, 1); hld.link(1, 1); for (int i = 1; i <= n; i++) hld.update(hld.id[i], hld.id[i], a[i]);
string op; for (int i = 0; i < q; i++) { cin >> op; if (op == "I") { cin >> u >> v >> w; hld.update_path(u, v, w); } elseif (op == "D") { cin >> u >> v >> w; hld.update_path(u, v, -w); } else { cin >> u; cout << hld.query(hld.id[u]) << endl; } } } }