Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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))));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment