Subtrees And Paths

                            Solution in C :

In   C++  :







#include<iostream>
#include<algorithm>
#include<cassert>
#include<fstream>
#include<cstring>
#include<vector>

#define PB push_back
#define DEBUG( x ) cout << #x << endl
#define foreach(it, c) for(__typeof (c).begin() it=(c).begin(); it!=(c).end(); it++)
#define  WAIT cout<<flush, system("PAUSE")
using namespace std;
const int oo = 1e9+100;
#define MAX 100100
#define MAX4 MAX*4


int N, Q, u, v, val;
vector< int > E[MAX];
int D[MAX], S[MAX], P[MAX], CH[MAX];
int lft[MAX], rgh[MAX];
int pos[MAX], chain[MAX], top[MAX], bot[MAX], csz[MAX], cnt, id=1, xtra_id=1;
string op;

int idx, l, r;
int tree[MAX4], xtra[MAX4], xtra_tree[MAX4], b[MAX4], e[MAX4];
void init(int n, int beg, int end){
b[n]=beg, e[n]=end;
if (beg==end){
return;
}
int m=beg + (end-beg)/2;
init(2*n,   beg,   m);
init(2*n+1, m+1, end);
}
int query_point(int n, int x){
if (b[n]==e[n])
return xtra_tree[n];

xtra_tree[2*n]   += xtra_tree[n];
xtra_tree[2*n+1] += xtra_tree[n];
xtra_tree[n]      = 0;

if (e[2*n] >= lft[x]) return query_point(2*n, x);
else                  return query_point(2*n+1, x);
}
void update_range(int n, int l, int r){
if (b[n]>r || e[n]<l)
return;
if (b[n]>=l && e[n]<=r){
xtra_tree[n] += val;
return;
}
update_range(2*n, l, r);
update_range(2*n+1, l, r);
}

void push(int n){
xtra[2*n]   += xtra[n];
xtra[2*n+1] += xtra[n];
xtra[n]      = 0;
}
int query(int n, int l, int r){
if (b[n]>r || e[n]<l)   
return -oo;
if (b[n]>=l && e[n]<=r){
return tree[n]+xtra[n];
}

push(n);
int la = query(2*n, l, r);
int ra = query(2*n+1, l, r);

tree[n] = max(tree[2*n]+xtra[2*n], tree[2*n+1]+xtra[2*n+1]);
return max(la, ra);
}
void update(int n, int l, int r){
if (b[n]>r || e[n]<l)   
return;
if (b[n]>=l && e[n]<=r){
xtra[n] += val;
return;
}


update(2*n, l, r);
update(2*n+1, l, r);

tree[n] = max(tree[2*n]+xtra[2*n], tree[2*n+1]+xtra[2*n+1]);
}

void DFS(int n, int p, int d){
D[n]=d;    P[n]=p;    S[n]=1;
lft[n] = xtra_id++;

foreach(it, E[n])
if (*it != p){
DFS(*it, n, d+1);
S[n] += S[*it];
if (S[*it]>S[CH[n]])
CH[n]=*it;
}
rgh[n] = xtra_id-1;
}
void HLD(int n){
pos[n] = id++;
chain[n]=cnt;
if (!csz[cnt]) 
top[cnt]=n, bot[cnt]=n;
else if (D[n]>D[bot[cnt]])
bot[cnt] = n;   
csz[cnt]++;


if (CH[n]) HLD(CH[n]);
foreach(it, E[n])
if (*it != P[n] && *it != CH[n]){
cnt++;
HLD(*it);
}
}
void Hquery(){
int sol = -oo;

while(chain[u] != chain[v]){

if (D[top[chain[u]]] < D[top[chain[v]]]) 
swap(u, v);


int curr = query(1, pos[top[chain[u]]], pos[u]);
curr += query_point(1, top[chain[u]]);

sol = max(sol, curr);
u = P[top[chain[u]]];
}
if (D[u] < D[v]) 
swap(u, v);

int curr = query(1, pos[v], pos[u]);
curr += query_point(1, top[chain[u]]);


sol = max(sol, curr);
cout << sol << "\n";
}
void Hupdate(){
if (u != top[chain[u]]){
update(1, pos[u], pos[bot[chain[u]]]);
}
update_range(1, lft[u], rgh[u]);
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

cin >> N;
for(int I=1; I<N; I++){
cin >> u >> v;
E[u].PB(v);
E[v].PB(u);
}
DFS(1, -1, 0);
HLD(1);
cnt++;
init(1, 1, N);

cin >> Q;
while(Q--){
cin >> op;
if (op == "add"){
cin >> u >> val;
idx = pos[u];
Hupdate();
} else {
assert(op == "max");
cin >> u >> v;
Hquery();
}
}

}









In    Java  :






import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.BitSet;
import java.util.InputMismatchException;

public class SubtreesAndPaths {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve () {
int n = ni ();
int [] from = new int [n - 1];
int [] to = new int [n - 1];
for (int i = 0; i <n - 1; i ++) {
from [i] = ni () - 1;
to [i] = ni () - 1;
}
int [] [] g = packU (n, from, to);
int [] [] pars = parents3 (g, 0);
int [] par = pars [0], ord = pars [1], dep = pars [2];
int [] clus = decomposeToHeavyLight (g, par, ord);
int [] [] cluspath = clusPaths (clus, ord);
int [] clusiind = clusIInd (cluspath, n);
int [] [] spar = logstepParents (par);

int u = cluspath.length;
StarrySkyTree [] ssts = new StarrySkyTree [u];
for (int i = 0; i <u; i ++) {
ssts [i] = new StarrySkyTree (cluspath [i] .length);
}

int [] [] rights = makeRights (g, par, 0);
int [] iord = rights [1], right = rights [2];
int [] ft = new int [n + 2];

for (int Q = ni (); Q> = 1; Q--) {
String com = ns ();
if (com.charAt (0) == 'a') {
int x = ni () - 1;
int v = ni ();
addFenwick (ft, right [iord [x]] + 1, v);
addFenwick (ft, iord [x], -v);
ssts [clus [x]]. add (clusiind [x], cluspath [clus [x]]. length, -v);
} else if (com.charAt (0) == 'm') {
int x = ni () - 1, y = ni () - 1;
int lca = lca2 (x, y, spar, dep);
int min = Integer.MAX_VALUE;
{
int cx = clus [x]; //
int ind = closing [x]; //
while (cx! = clus [lca]) {
int con = par [cluspath [cx] [0]];
int offset = con == -1? 0: sumFenwick (ft, iord [con]);
min = Math.min (min, ssts [cx] .min (0, ind + 1) + offset);

ind = closing [con];
cx = clus [con];
}

int con = par [cluspath [cx] [0]];
int offset = con == -1? 0: sumFenwick (ft, iord [con]);
min = Math.min (min, ssts [cx] .min (closing [lca], ind + 1) + offset);
}
{
int cx = clus [y]; //
int ind = closing [y]; //
while (cx! = clus [lca]) {
int con = par [cluspath [cx] [0]];
int offset = con == -1? 0: sumFenwick (ft, iord [con]);
min = Math.min (min, ssts [cx] .min (0, ind + 1) + offset);

ind = closing [con];
cx = clus [con];
}

int con = par [cluspath [cx] [0]];
int offset = con == -1? 0: sumFenwick (ft, iord [con]);
min = Math.min (min, ssts [cx] .min (closing [lca], ind + 1) + offset);
}
out.println (-min);
} else {
throw new RuntimeException ();
}
}
}

public static int [] sortByPreorder (int [] [] g, int root) {
int n = g.length;
int [] stack = new int [n];
int [] ord = new int [n];
BitSet ved = new BitSet ();
stack [0] = root;
int p = 1;
int r = 0;
ved.set (root);
while (p> 0) {
int cur = stack [p - 1];
ord [r ++] = cur;
p--;
for (int e: g [cur]) {
if (! ved.get (e)) {
stack [p ++] = e;
ved.set (e);
}
}
}
return ord;
}

public static int [] [] makeRights (int [] [] g, int [] par, int root) {
int n = g.length;
int [] ord = sortByPreorder (g, root);
int [] iord = new int [n];
for (int i = 0; i <n; i ++)
iord [ord [i]] = i;

int [] right = new int [n];
for (int i = n - 1; i> = 0; i--) {
int v = i;
for (int e: g [ord [i]]) {
if (e! = par [ord [i]]) {
v = Math.max (v, right [iord [e]]);
}
}
right [i] = v;
}
return new int [] [] {ord, iord, right};
}

public static int sumFenwick (int [] ft, int i) {
int sum = 0;
for (i ++; i> 0; i - = i & -i)
sum + = ft [i];
return sum;
}

public static void addFenwick (int [] ft, int i, int v) {
if (v == 0 || i <0)
return;
int n = ft.length;
for (i ++; i <n; i + = i & -i)
ft [i] + = v;
}

public static class StarrySkyTree {
public int M, H, N;
public int [] st;
public int [] plus;
public int I = Integer.MAX_VALUE / 2; // I + plus <int

public StarrySkyTree (int n) {
N = n;
M = Integer.highestOneBit (Math.max (n - 1, 1)) << 2;
H = M >>> 1;
st = new int [M];
plus = new int [H];
}

public StarrySkyTree (int [] a) {
N = a.length;
M = Integer.highestOneBit (Math.max (N - 1, 1)) << 2;
H = M >>> 1;
st = new int [M];
for (int i = 0; i <N; i ++) {
st [H + i] = a [i];
}
plus = new int [H];
Arrays.fill (st, H + N, M, I);
for (int i = H - 1; i> = 1; i--)
propagate (s);
}

private void propagate (int i) {
st [i] = Math.min (st [2 * i], st [2 * i + 1]) + plus [i];
}

public void add (int l, int r, int v) {
if (l <r)
add (l, r, v, 0, H, 1);
}

private void add (int l, int r, int v, int cl, int cr, int cur) {
if (l <= cl && cr <= r) {
if (cur> = H) {
st [cur] + = v;
} else {
plus [cur] + = v;
propagate (ass);
}
} else {
int mid = cl + cr >>> 1;
if (cl <r && l <mid) {
add (l, r, v, cl, mid, 2 * cur);
}
if (mid <r && l <cr) {
add (l, r, v, mid, cr, 2 * cur + 1);
}
propagate (ass);
}
}

public int min (int l, int r) {
return l> = r? I: min (l, r, 0, H, 1);
}

private int min (int l, int r, int cl, int cr, int cur) {
if (l <= cl && cr <= r) {
return st [cur];
} else {
int mid = cl + cr >>> 1;
int ret = I;
if (cl <r && l <mid) {
ret = Math.min (ret, min (l, r, cl, mid, 2 * cur));
}
if (mid <r && l <cr) {
ret = Math.min (ret, min (l, r, mid, cr, 2 * cur + 1));
}
return ret + plus [cur];
}
}

public void fall (int i) {
if (i <H) {
if (2 * i <H) {
plus [2 * i] + = plus [i];
plus [2 * i + 1] + = plus [i];
}
st [2 * i] + = plus [i];
st [2 * i + 1] + = plus [i];
plus [i] = 0;
}
}

public int firstle (int l, int v) {
int cur = H + 1;
for (int i = 1, j = Integer.numberOfTrailingZeros (H) - 1; i <= cur; j--) {
fall (i);
i = i * 2 | cur >>> j & 1;
}
while (true) {
fall (cur);
if (st [cur] <= v) {
if (cur <H) {
cur = 2 * cur;
} else {
return cur - H;
}
} else {
cur ++;
if ((cur & cur - 1) == 0)
return -1;
cur = cur >>> Integer.numberOfTrailingZeros (cur);
}
}
}

public int lastle (int l, int v) {
int cur = H + 1;
for (int i = 1, j = Integer.numberOfTrailingZeros (H) - 1; i <= cur; j--) {
fall (i);
i = i * 2 | cur >>> j & 1;
}
while (true) {
fall (cur);
if (st [cur] <= v) {
if (cur <H) {
cur = 2 * cur + 1;
} else {
return cur - H;
}
} else {
if ((cur & cur - 1) == 0)
return -1;
cur = cur >>> Integer.numberOfTrailingZeros (cur);
cur--;
}
}
}

public int [] toArray () {
return toArray (1, 0, H, new int [H]);
}

private int [] toArray (int cur, int l, int r, int [] ret) {
if (r - l == 1) {
ret [cur - H] = st [cur];
} else {
toArray (2 * cur, l, l + r >>> 1, ret);
toArray (2 * cur + 1, l + r >>> 1, r, ret);
for (int i = l; i <r; i ++)
ret [i] + = plus [cur];
}
return ret;
}
}

static int [] [] packU (int n, int [] from, int [] to) {
int [] [] g = new int [n] [];
int [] p = new int [n];
for (int f: from)
p [f] ++;
for (int t: to)
p [t] ++;
for (int i = 0; i <n; i ++)
g [i] = new int [p [i]];
for (int i = 0; i <from.length; i ++) {
g [from [i]] [- p [from [i]]] = to [i];
g [to [i]] [- p [to [i]]] = from [i];
}
return g;
}

public static int [] [] parents3 (int [] [] g, int root) {
int n = g.length;
int [] par = new int [n];
Arrays.fill (par, -1);

int [] depth = new int [n];
depth [0] = 0;

int [] q = new int [n];
q [0] = root;
for (int p = 0, r = 1; p <r; p ++) {
int cur = q [p];
for (int nex: g [cur]) {
if (par [cur]! = nex) {
q [r ++] = nex;
par [nex] = cur;
depth [nex] = depth [cur] + 1;
}
}
}
return new int [] [] {par, q, depth};
}

public static int lca2 (int a, int b, int [] [] spar, int [] depth) {
if (depth [a] <depth [b]) {
b = ancestor (b, depth [b] - depth [a], spar);
} else if (depth [a]> depth [b]) {
a = ancestor (a, depth [a] - depth [b], spar);
}

if (a == b)
return a;
int sa = a, sb = b;
for int low = 0, high = depth [a], t = Integer.highestOneBit (high), k = Integer
.numberOfTrailingZeros (t); t> 0; t >>> = 1, k--) {
if ((low ^ high)> = t) {
if (spar [k] [sa]! = spar [k] [sb]) {
low | = t;
sa = spar [k] [sa];
sb = spar [k] [sb];
} else {
high = low | t - 1;
}
}
}
return spar [0] [sa];
}

protected static int ancestor (int a, int m, int [] [] spar) {
for (int i = 0; m> 0 && a! = -1; m >>> = 1, i ++) {
if ((m & 1) == 1)
a = spar [i] [a];
}
return a;
}

public static int [] [] logstepParents (int [] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros (Integer.highestOneBit (n - 1)) + 1;
int [] [] pars = new int [m] [n];
pars [0] = par;
for (int j = 1; j <m; j ++) {
for (int i = 0; i <n; i ++) {
pars [j] [i] = pars [j - 1] [i] == -1? -1: pars [j - 1] [pars [j - 1] [i]];
}
}
return pars;
}

public static int [] decomposeToHeavyLight (int [] [] g, int [] par, int [] ord) {
int n = g.length;
int [] size = new int [n];
Arrays.fill (size, 1);
for (int i = n - 1; i> 0; i--)
size [par [ord [i]]] + = size [ord [i]];

int [] clus = new int [n];
Arrays.fill (clus, -1);
int p = 0;
outer: for (int i = 0; i <n; i ++) {
int u = ord [i];
if (clus [u] == -1)
clus [u] = p ++;
for (int v: g [u]) {
if (par [u]! = v && size [v]> = size [u] / 2) {
clus [v] = clus [u];
continue outer;
}
}
for (int v: g [u]) {
if (par [u]! = v) {
clus [v] = clus [u];
break;
}
}
}
return clus;
}

public static int [] [] clusPaths (int [] clus, int [] ord) {
int n = clus.length;
int [] rp = new int [n];
int sup = 0;
for (int i = 0; i <n; i ++) {
rp [clus [i]] ++;
sup = Math.max (sup, clus [i]);
}
sup ++;

int [] [] row = new int [sup] [];
for (int i = 0; i <sup; i ++)
row [i] = new int [rp [i]];

for (int i = n - 1; i> = 0; i--) {
row [clus [ord [i]]] [- rp [clus [ord [i]]]] = ord [i];
}
return row;
}

public static int [] clusIInd (int [] [] clusPath, int n) {
int [] iind = new int [n];
for (int [] path: clusPath) {
for (int i = 0; i <path.length; i ++) {
iind [path [i]] = i;
}
}
return iind;
}

public static void main (String [] args) throws Exception {
long S = System.currentTimeMillis ();
is = INPUT.isEmpty ()? System.in: new ByteArrayInputStream (INPUT.getBytes ());
out = new PrintWriter (System.out);

solve ();
out.flush ();
long G = System.currentTimeMillis ();
tr (G-S + "ms");
}

private static boolean eof () {
if (lenbuf == -1)
return true;
int lptr = ptrbuf;
while (lptr <lenbuf)
if (! isSpaceChar (inbuf [lptr ++]))
return false;

try {
is.mark (1000);
while (true) {
int b = is.read ();
if (b == -1) {
is.reset ();
return true;
} else if (! isSpaceChar (b)) {
is.reset ();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte [] inbuf = new byte [1024];
static int lenbuf = 0, ptrbuf = 0;

private static int readByte () {
if (lenbuf == -1)
throw new InputMismatchException ();
if (ptrbuf> = lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read (inbuf);
} catch (IOException e) {
throw new InputMismatchException ();
}
if (lenbuf <= 0)
return -1;
}
return inbuf [ptrbuf ++];
}

private static boolean isSpaceChar (int c) {
return! (c> = 33 && c <= 126);
}

private static int skip () {
int b;
while ((b = readByte ())! = -1 && isSpaceChar (b))
;
return b;
}

private static double nd () {
return Double.parseDouble (ns ());
}

private static char nc () {
return (char) skip ();
}

private static String ns () {
int b = skip ();
StringBuilder sb = new StringBuilder ();
while (! (isSpaceChar (b))) {// when nextLine, (isSpaceChar (b) && b! = '')
sb.appendCodePoint (b);
b = readByte ();
}
return sb.toString ();
}

private static char [] ns (int n) {
char [] buf = new char [n];
int b = skip (), p = 0;
while (p <n &&! (isSpaceChar (b))) {
buf [p ++] = (char) b;
b = readByte ();
}
return n == p? buf: Arrays.copyOf (buf, p);
}

private static char [] [] nm (int n, int m) {
char [] [] map = new char [n] [];
for (int i = 0; i <n; i ++)
map [i] = ns (m);
return map;
}

private static int [] na (int n) {
int [] a = new int [n];
for (int i = 0; i <n; i ++)
a [i] = ni ();
return a;
}

private static int ni () {
int num = 0, b;
boolean minus = false;
while ((b = readByte ())! = -1 &&! ((b> = '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte ();
}

while (true) {
if (b> = '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus? -num: num;
}
b = readByte ();
}
}

private static long nl () {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte ())! = -1 &&! ((b> = '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte ();
}

while (true) {
if (b> = '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus? -num: num;
}
b = readByte ();
}
}

private static void tr (Object ... o) {
if (INPUT.length ()! = 0)
System.out.println (Arrays.deepToString (o));
}
}









In   C   :







#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1000000007
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
typedef struct _tree{
int max;
int off;
} tree;
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void dfs2(int u);
void preprocess();
int lca(int a,int b);
int sum(int v,int tl,int tr,int l,int r,tree *t);
int min(int x,int y);
int max(int x,int y);
int solve(int x,int ancestor);
void range_update (int v, 
int tl, int tr, int pos1, 
int pos2, int new_val,tree *t);
void push(int v,int tl,int tr,tree *t);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
char str[10];
int N,NN,cn,level[100000],DP[18][100000],
subtree_size[100000],special[100000],
node_chain[100000],node_idx[100000],
chain_head[100000],chain_len[100000]={0};
int *range_upt,chain_order[100000],
node_begin[100000],node_end[100000],con=0;
lnode *table[100000]={0};
tree *chain[100000];

int main(){
int Q,x,y,i;
scanf("%d",&N);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
preprocess();
scanf("%d",&Q);
while(Q--){
scanf("%s",str);
switch(str[0]){
case 'a':
scanf("%d%d",&x,&y);
range_increment(node_begin[x-1],node_end[x-1],y);
if(node_idx[x-1])
range_update(1,0,chain_len[node_chain[x-1]]-1,
node_idx[x-1],chain_len[node_chain[x-1]]-1,y,
chain[node_chain[x-1]]);
break;
default:
scanf("%d%d",&x,&y);
i=lca(x-1,y-1);
printf("%d\n",max(solve(x-1,i),solve(y-1,i)));
}
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int u){
lnode *x;
subtree_size[u]=1;
special[u]=-1;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
subtree_size[u]+=subtree_size[x->x];
if(special[u]==-1 ||
 subtree_size[x->x]>subtree_size[special[u]])
special[u]=x->x;
}
return;
}
void dfs1(int u,int c){
lnode *x;
node_chain[u]=c;
node_idx[u]=chain_len[c]++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
if(x->x==special[u])
dfs1(x->x,c);
else{
chain_head[cn]=x->x;
dfs1(x->x,cn++);
}
return;
}
void dfs2(int u){
lnode *x;
node_begin[u]=con;
if(!node_idx[u])
chain_order[node_chain[u]]=con++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
dfs2(x->x);
node_end[u]=con-1;
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i=1;i<18;i++)
for(j=0;j<N;j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
cn=1;
chain_head[0]=0;
dfs1(0,0);
for(i=0;i<cn;i++){
chain[i]=(tree*)malloc(4*chain_len[i]*sizeof(tree));
memset(chain[i],0,4*chain_len[i]*sizeof(tree));
}
range_upt=malloc(4*cn*sizeof(int));
init(cn);
dfs2(0);
return;
}
int lca(int a,int b){
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i=0;i<18;i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b)return a;
for(i=17;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
int sum(int v,int tl,int tr,int l,int r,tree *t){
push(v,tl,tr,t);
if(l>r)
return -INF;
if(l==tl && r==tr)
return t[v].max;
int tm=(tl+tr)/2;
return max(sum(v*2,tl,tm,l,min(r,tm),t),
sum(v*2+1,tm+1,tr,max(l,tm+1),r,t));
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y){
return (x>y)?x:y;
}
int solve(int x,int ancestor){
int ans=-INF;
while(node_chain[x]!=node_chain[ancestor]){
ans=max(ans,sum(1,0,chain_len[node_chain[x]]-1,0,
node_idx[x],chain[node_chain[x]])+
query(chain_order[node_chain[x]]));
x=DP[0][chain_head[node_chain[x]]];
}
ans=max(ans,sum(1,0,chain_len[node_chain[x]]-1,
node_idx[ancestor],node_idx[x],
chain[node_chain[x]])+
query(chain_order[node_chain[x]]));
return ans;
}
void range_update (int v, int tl, 
int tr, int pos1, int pos2, int new_val,tree *t) {
push(v,tl,tr,t);
if(pos2<tl || pos1>tr)
return;
if (pos1<=tl && pos2>=tr)
t[v].off += new_val;
else {
int tm = (tl + tr) / 2;
range_update (v*2, tl, tm, pos1,pos2, new_val,t);
range_update (v*2+1, tm+1, tr, pos1,pos2, new_val,t);
push(v*2,tl,tm,t);
push(v*2+1,tm+1,tr,t);
t[v].max = max(t[v*2].max , t[v*2+1].max);
}
}
void push(int v,int tl,int tr,tree *t){
if(!t[v].off)
return;
t[v].max+=t[v].off;
if(tl!=tr){
t[2*v].off+=t[v].off;
t[2*v+1].off+=t[v].off;
}
t[v].off=0;
return;
}
void init( int n ){
NN = 1;
while( NN < n ) NN *= 2;
int i;
for( i = 1; i < NN + n; i++ ) range_upt[i] = 0;
}
void range_increment( int i, int j, int val ){
for( i += NN, j += NN; i <= j; 
i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) range_upt[i] += val;
if( j % 2 == 0 ) range_upt[j] += val;
}
}
int query( int i ){
int ans = 0,j;
for( j = i + NN; j; j /= 2 ) ans += range_upt[j];
return ans;
}








In   Python3  :







n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]

for i in range(n-1):
    a, b = [int(x)-1 for x in input().split()]
    connections[a].append(b)
    connections[b].append(a)

# iterative with queue
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
    node, level = queue.popleft()
    visited.add(node)
    levels[node] = level
    for i in connections[node]:
        if i not in visited:
            parents[i] = node
            queue.append((i, level+1))



def findcommonancestor(a, b):
    if levels[a] > levels[b]:
        for _ in range(levels[a] - levels[b]):
            a = parents[a]
    elif levels[b] > levels[a]:
        for _ in range(levels[b] - levels[a]):
            b = parents[b]
    while a != b:
        a, b = parents[a], parents[b]
    return a

def findprevvals(a):
    val = 0
    a = parents[a]
    while a is not None:
        val += values[a]
        a = parents[a]
    return val

def findprevmax(a, stop):
    max_a = values[a]
    while a != stop:
        a = parents[a]
        if max_a > 0:
            max_a += values[a]
        else:
            max_a = values[a]
    return max_a

def findmax(a, b):
    common_ancestor = findcommonancestor(a, b)
    ancestor_val = findprevvals(common_ancestor)
    max_a = findprevmax(a, common_ancestor)
    max_b = findprevmax(b, common_ancestor)
    return max(max_a, max_b) + ancestor_val
    
def addtosubtree(root, n):
    values[root] += n

q = int(input())
for i in range(q):
    inp = input().split()
    if inp[0] == 'add':
        addtosubtree(int(inp[1])-1, int(inp[2]))
    else:
        print(findmax(int(inp[1])-1, int(inp[2])-1))