POJ 2763 题解 (树链剖分维护边权)

题目

传送门

题意

给n个点，n-1条边，初始点为s，q个询问，操作0是s到u的距离，操作1是改变第i条边的权值为w。

(边权模板题)

题解

将每条边的权值存到更深的点上，跑树链剖分即可。

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 100005;
int w[MAXN], rk[MAXN];
int n, s, q;
struct sgm {
    int l, r;
    long long sum;
    long long lazy;
} sgmt[MAXN << 2];
inline void push_up ( int rt ) {
    sgmt[rt].sum = sgmt[rt << 1].sum + sgmt[rt << 1 | 1].sum;
}
void build ( int rt, int l, int r ) {
    sgmt[rt].l = l;
    sgmt[rt].r = r;
    sgmt[rt].lazy = 0;
    if ( l == r ) {
        sgmt[rt].sum = w[l];
        return;
    }
    int mid = ( l + r ) >> 1;
    build ( rt << 1, l, mid );
    build ( rt << 1 | 1, mid + 1, r );
    push_up ( rt );
}
void update ( int rt, int l, int r, long long c ) {
    if ( l <= sgmt[rt].l && sgmt[rt].r <= r ) {
        sgmt[rt].sum += c * ( sgmt[rt].r - sgmt[rt].l + 1 );
        sgmt[rt].lazy += c;
        return;
    }
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        update ( rt << 1, l, r, c );
    }
    if ( mid < r ) {
        update ( rt << 1 | 1, l, r, c );
    }
    push_up ( rt );
}
long long query ( int rt, int l, int r ) {
    if ( l <= sgmt[rt].l && sgmt[rt].r <= r ) {
        return sgmt[rt].sum;
    }
    long long ans = sgmt[rt].lazy * ( min ( sgmt[rt].r, r ) - max ( sgmt[rt].l, l ) + 1 );
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        ans += query ( rt << 1, l, r );
    }
    if ( mid < r ) {
        ans += query ( rt << 1 | 1, l, r );
    }
    return ans;
}
int Head[MAXN << 1], ver[MAXN << 1], nxt[MAXN << 1];
int E;
void addedge ( int u, int v ) {
    ver[E] = v;
    nxt[E] = Head[u];
    Head[u] = E++;
}
int cnt;
int son[MAXN], size[MAXN], d[MAXN], fa[MAXN], top[MAXN], id[MAXN];
void dfs1 ( int f, int u, int depth ) {
    size[u] = 1;
    son[u] = 0;
    d[u] = depth;
    fa[u] = f;
    for ( int i = Head[u]; ~i; i = nxt[i] ) {
        int v = ver[i];
        if ( v == f ) {
            continue;
        }
        dfs1 ( u, v, depth + 1 );
        size[u] += size[v];
        if ( size[v] > size[son[u]] ) {
            son[u] = v;
        }
    }
}
void dfs2 ( int f, int u ) {
    top[u] = f;
    id[u] = ++cnt;
    rk[cnt] = u;
    if ( !son[u] ) {
        return;
    }
    dfs2 ( f, son[u] );
    for ( int i = Head[u]; ~i; i = nxt[i] ) {
        int v = ver[i];
        if ( v == fa[u] || v == son[u] ) {
            continue;
        }
        dfs2 ( v, v );
    }
}
void pathadd ( int x, int y, int k ) {
    int fx = top[x], fy = top[y];
    while ( id[fx] != id[fy] ) {
        if ( d[fx] > d[fy] ) {
            update ( 1, id[fx], id[x], k );
            x = fa[fx];
            fx = top[x];
        } else {
            update ( 1, id[fy], id[y], k );
            y = fa[fy];
            fy = top[y];
        }
    }
    if ( id[x] > id[y] ) {
        update ( 1, id[y], id[x], k );
    } else {
        update ( 1, id[x], id[y], k );
    }
    return;
}
long long pathsum ( int x, int y ) {
    long long ans = 0;
    int fx = top[x], fy = top[y];
    while ( id[fx] != id[fy] ) {
        if ( d[fx] > d[fy] ) {
            ans += query ( 1, id[fx], id[x] );
            x = fa[fx];
            fx = top[x];
        } else {
            ans += query ( 1, id[fy], id[y] );
            y = fa[fy];
            fy = top[y];
        }
    }
    if ( id[x] > id[y] ) {
        ans += query ( 1, id[son[y]], id[x] );
    } else if ( id[y] > id[x] ) {
        ans += query ( 1, id[son[x]], id[y] );
    }
    return ans;
}
struct edge {
    int u, v, w;
    void input() {
        scanf ( "%d %d %d", &u, &v, &w );
        addedge ( u, v );
        addedge ( v, u );
    }
} e[MAXN];
int x, y, k;
int main() {
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    while ( ~scanf ( "%d %d %d", &n, &q, &s ) ) {
        E = 0;
        cnt = 0;
        memset ( Head, -1, sizeof ( Head ) );
        for ( int i = 1; i < n; i++ ) {
            e[i].input();
        }
        dfs1 ( 0, 1, 1 );
        dfs2 ( 1, 1 );
        for ( int i = 1; i < n; i++ ) {
            if ( d[e[i].u] > d[e[i].v] ) {
                swap ( e[i].u, e[i].v );
            }
            w[id[e[i].v]] = e[i].w;
        }
        w[1] = 0;
        build ( 1, 1, n );
        int com, w, ith;
        for ( int i = 0; i < q; i++ ) {
            scanf ( "%d", &com );
            if ( com ) {
                scanf ( "%d %d", &ith, &w );
                pathadd ( e[ith].v, e[ith].v, w - e[ith].w );
                e[ith].w = w;
            } else {
                scanf ( "%d", &w );
                printf ( "%lld\n", pathsum ( s, w ) );
                s = w;
            }
        }
    }
    return 0;
}