Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <map>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <unordered_map>
- #include <numeric>
- #include <iomanip>
- using namespace std;
- #define pii pair<int , int>
- #define ll long long
- #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
- const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
- const long long dl[2] = {1, -1};
- const long long MOD = 1000000007;
- const long long MAXN = 100005;
- int N, M, sz[MAXN], par[MAXN], dep[MAXN], heavy[MAXN], idx[MAXN], head[MAXN], seg[MAXN * 4], cost[MAXN], tmp_cost[MAXN], cur_idx = 1;
- pair<pii, int> edge[MAXN];
- int child_of[MAXN];
- vector<pii> v[MAXN];
- void dfs(int cur, int p, int d){
- int max_sz = 0;
- int max_c = -1;
- sz[cur] = 1;
- par[cur] = p;
- dep[cur] = d;
- for(auto x : v[cur]){
- if(x.first != p){
- tmp_cost[x.first] = x.second;
- dfs(x.first, cur, d + 1);
- sz[cur] += sz[x.first];
- if(sz[x.first] > max_sz){
- max_sz = sz[x.first];
- max_c = x.first;
- }
- }
- }
- heavy[cur] = max_c;
- }
- void decompose(int cur, int h){
- head[cur] = h;
- idx[cur] = cur_idx;
- cost[idx[cur]] = tmp_cost[cur];
- cur_idx++;
- if(heavy[cur] != -1){
- decompose(heavy[cur], h);
- }
- for(auto x : v[cur]){
- if(x.first != par[cur] && x.first != heavy[cur]){
- decompose(x.first, x.first);
- }
- }
- }
- void build(int x, int s, int e){
- if(s == e){
- seg[x] = cost[s];
- return;
- }
- int mid = (s + e)/2;
- build(x * 2, s, mid);
- build(x * 2 + 1, mid + 1, e);
- seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
- }
- void update(int x, int s, int e, int id, int val){
- if(id < s || e < id) return;
- if(s == e){
- seg[x] = val;
- return;
- }
- int mid = (s + e)/2;
- update(x * 2, s, mid, id, val);
- update(x * 2 + 1, mid + 1, e, id, val);
- seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
- }
- int query(int x, int s, int e, int a, int b){
- if(b < s || e < a) return 0;
- if(a <= s && e <= b){
- return seg[x];
- }
- int mid = (s + e)/2;
- return max(query(x * 2, s, mid, a, b), query(x * 2 + 1, mid + 1, e, a, b));
- }
- int solve(int a, int b){
- int ret = 0;
- while(head[a] != head[b]){
- if(dep[head[a]] > dep[head[b]]) swap(a, b);
- ret = max(ret, query(1, 1, N, idx[head[b]], idx[b]));
- b = par[head[b]];
- }
- if(dep[a] > dep[b]){
- swap(a, b);
- }
- ret = max(ret, query(1, 1, N, idx[a] + 1, idx[b]));
- return ret;
- }
- int main() {
- FAST;
- cin >> N;
- for(int i = 1; i < N; i++){
- cin >> edge[i].first.first >> edge[i].first.second >> edge[i].second;
- v[edge[i].first.first].push_back({edge[i].first.second, edge[i].second});
- v[edge[i].first.second].push_back({edge[i].first.first, edge[i].second});
- }
- dfs(1, 0, 1);
- decompose(1, 1);
- build(1, 1, N);
- for(int i = 1; i < N; i++){
- if(par[edge[i].first.first] == edge[i].first.second){
- child_of[i] = edge[i].first.first;
- }
- else{
- child_of[i] = edge[i].first.second;
- }
- }
- cin >> M;
- for(int x, y, z, i = 0; i < M; i++){
- cin >> x >> y >> z;
- if(x == 1){
- int ver = child_of[y];
- update(1, 1, N, idx[ver], z);
- }
- else{
- if(y == z){
- cout << "0\n";
- }
- else{
- cout << solve(y, z) << "\n";
- }
- }
- }
- }
- /*
- 3
- 1 2 1
- 2 3 2
- 3
- 2 1 2
- 1 1 3
- 2 1 2
- */
- /*
- 13
- 1 2 1
- 1 3 2
- 2 4 3
- 2 5 4
- 3 6 5
- 5 7 6
- 5 8 7
- 6 9 8
- 6 10 9
- 9 11 10
- 9 12 11
- 10 13 12
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement