Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _ijps 0
- #define _ALLOW_RTCc_IN_STL
- #define _CRT_SECURE_NO_DEPRECATE
- //#pragma comment(linker, "/STACK:667772160")
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <time.h>
- #include <map>
- #include <set>
- #include <deque>
- #include <cstdio>
- #include <cstdlib>
- #include <unordered_map>
- #include <unordered_set>
- #include <bitset>
- #include <algorithm>
- #include <string>
- #include <fstream>
- #include <assert.h>
- #include <list>
- #include <cstring>
- #include <queue>
- using namespace std;
- #define name "treepathadd"
- typedef long long ll;
- struct __isoff {
- __isoff() {
- if(_ijps)
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);//, freopen("test.txt", "w", stderr);
- else freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);
- //ios_bsume::sync_with_stdio(0);
- //srand(time(0));
- srand('C' + 'T' + 'A' + 'C' + 'Y' + 'M' + 'B' + 'A');
- }
- ~__isoff() {
- //if(_ijps) cout<<times<<'\n';
- }
- } __osafwf;
- const ll inf = (ll)2e18;
- const int dd = (int)6e5 + 5;
- const int super = 2123123;
- ll T[dd * 4];
- ll A[dd * 4];
- ll S[dd * 4];
- void build(int v, int l, int r, vector<ll> const& P) {
- S[v] = super;
- if(l == r) {
- T[v] = P[l];
- return;
- }
- int s = (l + r) / 2;
- build(v * 2, l, s, P);
- build(v * 2 + 1, s + 1, r, P);
- T[v] = T[v * 2] + T[v * 2 + 1];
- }
- void sset(int v, int l, int r, int lq, int rq, ll x) {
- if(lq > rq) {
- return;
- }
- if(l == lq && r == rq) {
- T[v] += x;
- return;
- }
- int s = (l + r) / 2;
- sset(v * 2, l, s, lq, min(rq, s), x);
- sset(v * 2 + 1, s + 1, r, max(lq, s + 1), rq, x);
- T[v] = T[v * 2] + T[v * 2 + 1];
- }
- ll get(int v, int l, int r, int lq, int rq) {
- if(lq > rq) {
- return 0;
- }
- if(l == lq && r == rq) {
- return T[v];
- }
- int s = (l + r) / 2;
- return get(v * 2, l, s, lq, min(rq, s)) +
- get(v * 2 + 1, s + 1, r, max(lq, s + 1), rq);
- }
- const int Df = 20;
- vector<int> P[dd];
- int Lca[Df][dd];
- int H[dd], L[dd], R[dd], tt;
- void dfs(int v, int p, int h) {
- L[v] = tt++;
- H[v] = h;
- Lca[0][v] = p;
- for(int i = 1; i < Df; i++) {
- Lca[i][v] = Lca[i - 1][Lca[i - 1][v]];
- }
- for(auto u : P[v]) {
- if(u != p) {
- dfs(u, v, h + 1);
- }
- }
- R[v] = tt++;
- }
- bool is(int a, int b) {
- return L[a] <= L[b] && R[b] <= R[a];
- }
- int lca(int a, int b) {
- if(is(a, b)) {
- return a;
- }
- if(is(b, a)) {
- return b;
- }
- for(int i = Df - 1; i >= 0; i--) {
- int c = Lca[i][a];
- if(!is(c, b)) {
- a = c;
- }
- }
- return Lca[0][a];
- }
- void add_p(int v, int x) {
- sset(1, 0, dd - 1, L[v], L[v], x);
- }
- void add_p(int a, int b, int x) {
- int c = lca(a, b);
- add_p(a, x);
- add_p(b, x);
- add_p(c, -x);
- if(c > 0) {
- add_p(Lca[0][c], -x);
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- int n;
- cin >> n;
- for(int i = 0; i < n - 1; i++) {
- int a, b;
- cin >> a >> b;
- a--, b--;
- P[a].push_back(b);
- P[b].push_back(a);
- }
- dfs(0, 0, 0);
- int m;
- cin >> m;
- for(int i = 0; i < m; i++) {
- char c;
- cin >> c;
- if(c == '+') {
- int a, b, x;
- cin >> a >> b >> x;
- a--, b--;
- add_p(a, b, x);
- }
- else {
- int a;
- cin >> a;
- a--;
- cout << get(1, 0, dd - 1, L[a], R[a]) << '\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement