提出 #39858019

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int maxlog = 17;
int n, b[maxn], dep[maxn], fa[maxn][maxlog + 1], sz[maxn], dfn[maxn], dfntimes;
ll tree[maxn];
vector<pair<int, int>> e[maxn];
pair<int, int> eg[maxn];
void dfs_pre(int u, int from) {
    dfn[u] = ++dfntimes;
    sz[u] = 1;
    fa[u][0] = from;
    dep[u] = dep[from] + 1;
    for(int i = 1; i <= maxlog; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(auto v : e[u]) {
        if(v.first == from) {
            continue;
        }
        b[v.first] = v.second;
        dfs_pre(v.first, u);
        sz[u] += sz[v.first];
    }
}
int LCA(int x, int y) {
    if(dep[x] < dep[y]) {
        swap(x, y);
    }
    for(int i = maxlog; i >= 0; i--) {
        if(dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
    }
    if(x == y) {
        return x;
    }
    for(int i = maxlog; i >= 0;i --) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
void update(int x, ll v) {
    for(; x <= n; x += x & (-x)) {
        tree[x] += v;
    }
}
ll query(int x) {
    ll res = 0;
    for(; x >= 1; x -= x & (-x)) {
        res += tree[x];
    }
    return res;
}
void modify(int x, int v) {
    update(dfn[x], v - b[x]);
    update(dfn[x] + sz[x], b[x] - v);
    b[x] = v;
}
ll getdis(int x) {
    return query(dfn[x]);
}
int main() {
#ifdef DEBUG
    freopen("1.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
        eg[i] = make_pair(u, v);
    }
    dfs_pre(1, 0);
    for(int i = 2; i <= n; i++) {
        update(dfn[i], b[i]);
        update(dfn[i] + sz[i], -b[i]);
    }
    int q;
    cin >> q;
    while(q--) {
        int o, x, y;
        cin >> o >> x >> y;
        if(o == 1) {
            int u = eg[x].first, v = eg[x].second;
            if(dep[u] < dep[v]) {
                modify(v, y);
            }
            else {
                modify(u, y);
            }
        }
        else {
            cout << getdis(x) + getdis(y) - getdis(LCA(x, y)) * 2 << '\n';
        }
    }
    return 0;
}

提出情報

ジャッジ結果