qtree.cpp

qtree.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
struct seg{
	int tree[270000], lim;
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
	}
	void add(int x, int v){
		x += lim;
		tree[x] = v;
		while(x > 1){
			x >>= 1;
			tree[x] = max(tree[2*x], tree[2*x+1]);
		}
	}
	int query(int s, int e){
		s += lim;
		e += lim;
		int ret = -1e9;
		while(s < e){
			if(s%2 == 1) ret = max(ret, tree[s++]);
			if(e%2 == 0) ret = max(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = max(ret, tree[s]);
		return ret;
	}
}seg;

int n, q;
int dep[100005], par[17][100005], pae[100005], sz[100005];
int comp[100005], head[100005], lab[100005], piv1, piv2;
vector<pi> gph[100005];

void dfs(int x, int p){
	sz[x] = 1;
	for(auto &i : gph[x]){
		if(i.second == p) continue;
		dep[i.second] = dep[x] + 1;
		par[0][i.second] = x;
		pae[i.second] = i.first;
		dfs(i.second, x); 
		sz[x] += sz[i.second];
	}
}

void hld(int x, int p){
	sort(gph[x].begin(), gph[x].end(), [&](const pi &a, const pi &b){
		return sz[a.second] > sz[b.second];
	});
	int fnd = -1;
	for(auto &i : gph[x]){
		if(i.second == p) continue;
		comp[i.second] = comp[x];
		lab[i.second] = ++piv2;
		fnd = i.second;
		hld(i.second, x);
		break;
	}
	for(auto &i : gph[x]){
		if(i.second == p || i.second == fnd) continue;
		comp[i.second] = ++piv1;
		head[piv1] = i.second;
		lab[i.second] = ++piv2;
		hld(i.second, x);
	}
}

int lca(int s, int e){
	if(dep[s] > dep[e]) swap(s, e);
	int dx = dep[e] - dep[s];
	for(int i=0; i<17; i++){
		if((dx >> i) & 1) e = par[i][e];
	}
	for(int i=16; i>=0; i--){
		if(par[i][s] != par[i][e]){
			s = par[i][s];
			e = par[i][e];
		}
	}
	if(s == e) return s;
	return par[0][s];
}

int query(int s, int e){
	int ret = 0;
	while(comp[s] != comp[e]){
		ret = max(ret, seg.query(lab[head[comp[s]]], lab[s]));
		s = par[0][head[comp[s]]];
	}
	ret = max(ret, seg.query(lab[e]+1, lab[s]));
	return ret;
}

int s[100005], e[100005], x[100005];

int main(){
	cin >> n;
	for(int i=1; i<n; i++){
		scanf("%d %d %d",&s[i],&e[i],&x[i]);
		gph[s[i]].push_back(pi(x[i], e[i]));
		gph[e[i]].push_back(pi(x[i], s[i]));
	}
	dfs(1, 0);
	for(int i=1; i<=16; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	head[1] = comp[1] = lab[1] = piv1 = piv2 = 1;
	hld(1, 0);
	seg.init(n);
	for(int i=2; i<=n; i++){
		seg.add(lab[i], pae[i]);
	}
	int q;
	cin >> q;
	while(q--){
		int t;
		scanf("%d",&t);
		if(t == 1){
			int v, w;
			scanf("%d %d",&v,&w);
			if(dep[s[v]] > dep[e[v]]) swap(s[v], e[v]);
			seg.add(lab[e[v]], w);
		}
		if(t == 2){
			int s, e;
			scanf("%d %d",&s,&e);
			printf("%d\n", max(query(s, lca(s, e)), query(e, lca(s, e))));
		}
	}
}