题目链接

Tree

题解

考虑树的欧拉序（即长度为 2N-1 的 DFS 序），用线段树维护每个点到根的距离，则修改边权的操作可以转化为区间加法。设树上有两点 u,v ，它们的欧拉序分别为 a,b ，那么这两点的最近公共祖先 p 的欧拉序 c 一定满足 a\leq c\leq b ，且 p 到根的距离一定是欧拉序在区间 [a,b] 内的点到根的距离中最小的（边权为正）。可以用线段树维护区间内的 max(Dist_a+Dist_b-2Dist_c), a\leq c\leq b 。

标程

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=110000;
const ll INF=1E18;
struct Range
{
    ll val, M, LM, MR, LMR;
    inline Range() { val=M=LM=MR=LMR=-INF; }
    inline Range(ll k)
    {
        val=k; M=-2*k; LM=MR=-k; LMR=0;
    }
    inline void operator += (ll k)
    {
        val+=k; M-=2*k; LM-=k; MR-=k;
    }
};
inline Range operator + (const Range& lhs, const Range& rhs)
{
    Range tmp;
    tmp.val=max(lhs.val, rhs.val);
    tmp.M=max(lhs.M, rhs.M);
    tmp.LM=max(max(lhs.LM, rhs.LM), lhs.val+rhs.M);
    tmp.MR=max(max(lhs.MR, rhs.MR), lhs.M+rhs.val);
    tmp.LMR=max(max(lhs.LMR, rhs.LMR), max(lhs.LM+rhs.val, lhs.val+rhs.MR));
    return tmp;
}
struct SegmentTree
{
    struct Node
    {
        int l, r;
        Range val; ll add;
    } tr[8*MAXN];
    #define lc (o<<1)
    #define rc (o<<1|1)
    inline void add(int o, ll k)
    {
        tr[o].val+=k; tr[o].add+=k;
    }
    inline void pushup(int o)
    {
        tr[o].val=tr[lc].val+tr[rc].val;
    }
    inline void pushdown(int o)
    {
        if (tr[o].add)
        {
            add(lc, tr[o].add);
            add(rc, tr[o].add);
            tr[o].add=0;
        }
    }
    void build(int o, int l, int r, ll* a)
    {
        tr[o].l=l; tr[o].r=r; tr[o].add=0;
        if (l==r)
        {
            tr[o].val=Range(a[l]);
            return;
        }
        int mid=l+r>>1;
        build(lc, l, mid, a);
        build(rc, mid+1, r, a);
        pushup(o);
    }
    void update(int o, int l, int r, ll k)
    {
        if (tr[o].l>r||tr[o].r<l) return;
        if (l<=tr[o].l&&tr[o].r<=r) { add(o, k); return; }
        pushdown(o);
        update(lc, l, r, k);
        update(rc, l, r, k);
        pushup(o);
    }
    Range query(int o, int l, int r)
    {
        if (tr[o].l>r||tr[o].r<l) return Range();
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].val;
        pushdown(o);
        return query(lc, l, r)+query(rc, l, r);
    }
    #undef lc
    #undef rc
} st;
struct Edge1
{
    int u, v, w;
    Edge1() {}
    Edge1(int a, int b, int c):
        u(a), v(b), w(c) {}
} e[MAXN];
struct Edge2
{
    int to, val;
    Edge2() { to=val=0; }
    Edge2(int v, int w): to(v), val(w) {}
};
int n, m, p;
int op[MAXN], cl[MAXN];
ll dis[2*MAXN];
vector<Edge2> g[MAXN];
void dfs(int u, int f, ll d)
{
    op[u]=++p; dis[p]=d;
    for (int i=0; i<g[u].size(); i++)
    {
        int v=g[u][i].to, w=g[u][i].val;
        if (v!=f) dfs(v, u, d+w), dis[++p]=d;
    }
    cl[u]=p;
}
ll queryRange(int l1, int r1, int l2, int r2)
{
    if (l1>l2) swap(l1, l2), swap(r1, r2);
    Range L, M, R; ll mx=0;
    if (r1<l2)
    {
        L=st.query(1, l1, r1);
        M=st.query(1, r1+1, l2-1);
        R=st.query(1, l2, r2);
        mx=max(mx, L.LM+R.val);
        mx=max(mx, L.val+R.MR);
        mx=max(mx, L.val+M.M+R.val);
    }
    else if (r2<=r1)
    {
        L=st.query(1, l1, l2-1);
        M=st.query(1, l2, r2);
        R=st.query(1, r2+1, r1);
        mx=max(mx, L.LM+M.val);
        mx=max(mx, L.val+M.MR);
        mx=max(mx, M.LM+R.val);
        mx=max(mx, M.val+R.MR);
        mx=max(mx, M.LMR);
    }
    else
    {
        L=st.query(1, l1, l2-1);
        M=st.query(1, l2, r1);
        R=st.query(1, r1+1, r2);
        mx=max(mx, L.LM+M.val);
        mx=max(mx, L.val+M.MR);
        mx=max(mx, M.LM+R.val);
        mx=max(mx, M.val+R.MR);
        mx=max(mx, L.LM+R.val);
        mx=max(mx, L.val+R.MR);
        mx=max(mx, L.val+M.M+R.val);
        mx=max(mx, M.LMR);
    }
    return mx;
}
inline void update(int i, int k)
{
    st.update(1, op[e[i].v], cl[e[i].v], k-e[i].w);
    e[i].w=k;
}
inline ll query1(int x, int y)
{
    return queryRange(op[x], cl[x], op[y], cl[y]);
}
inline ll query2(int x, int a, int b)
{
    return max(queryRange(op[x], cl[x], op[a], op[a]),
               queryRange(op[x], cl[x], op[b], op[b]));
}
int main()
{
//  freopen("tree.in", "r", stdin);
//  freopen("tree.out", "w", stdout);
    scanf("%d%d", &n, &m); p=0;
    for (int i=1; i<n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[i]=Edge1(u, v, w);
        g[u].push_back(Edge2(v, w));
        g[v].push_back(Edge2(u, w));
    }
    p=0; dfs(1, 0, 0);
    for (int i=1; i<n; i++)
        if (op[e[i].u]>op[e[i].v])
            swap(e[i].u, e[i].v);
    st.build(1, 1, p, dis);
    for (int i=1; i<=m; i++)
    {
        int opt, x, y, a, b, k;
        scanf("%d", &opt);
        switch (opt)
        {
            case 1:
                scanf("%d%d", &x, &k);
                update(x, k);
                break;
            case 2:
                scanf("%d%d", &x, &y);
                printf("%lld\n", query1(x, y));
                break;
            case 3:
                scanf("%d%d%d", &x, &a, &b);
                printf("%lld\n", query2(x, a, b));
                break;
        }
    }
    return 0;
}