You are viewing a single comment's thread. Return to all comments →
C++ solution
#include <bits/stdc++.h> using namespace std; #define foreach(i, x) for(type(x)i = x.begin(); i != x.end(); i++) #define FOR(ii, aa, bb) for(int ii = aa; ii <= bb; ii++) #define ROF(ii, aa, bb) for(int ii = aa; ii >= bb; ii--) #define type(x) __typeof(x.begin()) #define pb push_back #define mp make_pair #define time something_awesome1 const int inf = 1e9; const int mod = 1e9 + 7; const int logN = 18; const int N = 1e5 + 5; int start[N], e[N], head[N], time, i, j, k, n, m, depth[N], lca[N][logN + 1]; int sum[N], x, y, t; char s[5]; vector<int> v[N]; class node{ public: int max, L; node(){max = L = 0;} } ST[4 * N]; node merge(int l, node x, node y){ node temp; temp.max = max(x.max, y.max); temp.max += l; temp.L = l; return temp; } node update(int k, int bas, int son, int x, int y, int t){ if(bas > y || son < x) return ST[k]; if(x <= bas && son <= y){ ST[k].L += t; ST[k].max += t; return ST[k]; } int orta = bas + son >> 1; return ST[k] = merge(ST[k].L, update(2 * k, bas, orta, x, y, t), update(2 * k + 1, orta + 1, son, x, y, t)); } int query(int k, int bas, int son, int x, int y){ if(bas > y || son < x) return -inf; if(x <= bas && son <= y) return ST[k].max; int orta = bas + son >> 1; return max(query(k + k, bas, orta, x, y), query(k + k + 1, orta + 1, son, x, y)) + ST[k].L; } int dfs(int node, int last){ lca[node][0] = last; foreach(it, v[node]) if(*it != last){ depth[*it] = depth[node] + 1; sum[node] += dfs(*it,node); } return ++sum[node]; } void dfs2(int node, int last, int s){ int temp = 0; start[node] = ++time; head[node] = s; foreach(it, v[node]) if(*it != last && sum[*it] > sum[temp]) temp = *it; if(temp) dfs2(temp, node, s); foreach(it, v[node]) if(*it != last && *it != temp) dfs2(*it, node, *it); e[node] = time; } int LCA(int x, int y){ if(depth[x] < depth[y]) swap(x, y); int diff = depth[x] - depth[y]; FOR(i, 0, logN) if(diff & (1 << i)) x = lca[x][i]; if(x == y) return x; ROF(i, logN, 0) if(lca[x][i] != lca[y][i]) x = lca[x][i], y = lca[y][i]; return lca[x][0]; } int que(int x,int y){ int mx = -inf; while(depth[x] >= depth[y]){ mx = max(mx, query(1, 1, n, max(start[head[x]], start[y]), start[x])); x = lca[head[x]][0]; } return mx; } int solve(int x,int y){ int l = LCA(x, y); return max(que(x, l), que(y, l)); } int main(){ scanf("%d", &n); FOR(i, 2, n){ scanf("%d %d", &x, &y); v[x].pb(y); v[y].pb(x); } depth[1] = 1; dfs(1, 0); dfs2(1, 0, 1); FOR(j, 1, logN) FOR(i, 1, n) lca[i][j] = lca[lca[i][j - 1]][j - 1]; scanf("%d", &m); FOR(i, 1, m){ scanf("%s", s); if(strcmp(s, "add") == 0){ scanf("%d %d", &x, &y); update(1, 1, n, start[x], e[x], y); } else{ scanf("%d %d", &x, &y); printf("%d\n", solve(x,y)); } } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Subtrees And Paths
You are viewing a single comment's thread. Return to all comments →
C++ solution