首页 > 代码库 > Poj2763Housewife Wind树链剖分

Poj2763Housewife Wind树链剖分

边查询,点更新的模板题。

#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>using namespace std;typedef long long LL;const int maxn = 222222;struct Node{    int to;int next;}e[maxn*2];#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int head[maxn];int son[maxn];int top[maxn];int father[maxn];int deep[maxn];int len;int z;int size[maxn];int pos[maxn];int sum[maxn<<2];void add(int from, int to){    e[len].to = to;    e[len].next = head[from];    head[from] = len++;}int edge[maxn][10];void init(int x){    son[x] = 0; size[x] = 1;    for (int i = head[x]; i != -1; i = e[i].next){        int cc = e[i].to;        if (cc == father[x]) continue;        deep[cc] = deep[x] + 1; father[cc] = x;        init(cc);        size[x] += size[cc];        if (size[son[x]] < size[cc]) son[x] = cc;    }}void dfs(int x, int tp){    pos[x] = ++z;top[x] = tp;    if (son[x]) dfs(son[x], tp);    for (int i = head[x]; i != -1; i = e[i].next){        int cc = e[i].to;        if (cc == father[x] || cc == son[x]) continue;        dfs(cc, cc);    }}void up(int rt){    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void update(int key, int ans, int l, int r, int rt){    if (l == r){        sum[rt] = ans; return;    }    int mid = (l + r) >> 1;    if (key <= mid) update(key, ans, lson);    else update(key, ans, rson);    up(rt);}int ask(int L, int R, int l, int r, int rt){    if (L <= l&&r <= R) return sum[rt];    int mid = (l + r) >> 1;    int ans = 0;    if (L <= mid) ans += ask(L, R, lson);    if (R > mid) ans += ask(L, R, rson);    return ans;}int gao(int x, int y){    int ans = 0;    int fx = top[x]; int fy = top[y];    while (fx != fy){        if (deep[fx] < deep[fy]){            swap(fx, fy); swap(x, y);        }        ans += ask(pos[fx], pos[x], 1, z, 1);        x = father[fx]; fx = top[x];    }    if (x == y) return ans;    if (deep[x]>deep[y]) swap(x, y);    ans += ask(pos[x] + 1, pos[y], 1, z, 1);    return ans;}int main(){    int n,q,s;    int a,b,c;    while (cin >> n >> q >> s){        memset(sum,0,sizeof(sum));        len = 0;z =0;        memset(head,-1,sizeof(head));        deep[s]=1 ;        for (int i = 1; i < n ; i++){            scanf("%d%d%d", &edge[i][0], &edge[i][1], &edge[i][2]);            add(edge[i][0], edge[i][1]); add(edge[i][1], edge[i][0]);        }        init(1); dfs(1, 1);        for (int i = 1; i < n ; i++){            int a = edge[i][0]; int b = edge[i][1]; int c = edge[i][2];            if (deep[a]>deep[b]) swap(edge[i][0], edge[i][1]);            update(pos[edge[i][1]], c, 1, z, 1);        }        while (q--){            scanf("%d", &a);            if (a == 0){                scanf("%d", &b);                int t = gao(b, s);                cout << t << endl;                s = b;            }            else {                scanf("%d%d", &b, &c);                edge[b][2] = c;                update(pos[edge[b][1]], c, 1, z, 1);            }        }    }    return 0;}

 

Poj2763Housewife Wind树链剖分