Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

LCA+线段树

Posted by sponge_wxy at 2015-05-08 12:01:07 on Problem 2763
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
const int inf  = 0x3f3f3f3f;
const int maxn = 100010;
const int maxm = 2*maxn;
const int D = 20;

int dep[maxn];
int dis[maxn];
int dp[maxn][20];
int first[maxn], second[maxn];
int N, Q, S;
int tot;

struct Edge {
    int u, v, w, next;
    Edge() {}
    Edge(int t_u, int t_v, int t_w, int t_next) : u(t_u), v(t_v), w(t_w), next(t_next) {}
}edges[2*maxn];
int head[maxn], edge_sum;

void init_graph() {
    tot = 0;
    edge_sum = 0;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w) {
    edges[edge_sum].u = u;
    edges[edge_sum].v = v;
    edges[edge_sum].w = w;
    edges[edge_sum].next = head[u];
    head[u] = edge_sum++;

    edges[edge_sum].u = v;
    edges[edge_sum].v = u;
    edges[edge_sum].w = w;
    edges[edge_sum].next = head[v];
    head[v] = edge_sum++;
}

void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    dp[u][0] = p;
    first[u] = ++tot;
    for(int i = 1; i < D; ++i) {
        dp[u][i] = dp[dp[u][i-1]][i-1];
    }
    for(int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].v;
        if(v == p) continue;
        dis[v] = dis[u] + edges[i].w;
        dfs(v, u);
    }
    second[u] = ++tot;
    return ;
}

int lca(int u, int v) {
    if(dep[u] > dep[v]) swap(u, v);
    int d = dep[v] - dep[u];
    for(int i = D - 1; i >= 0; --i) {
        if(d&(1<<i)) {
            v = dp[v][i];
        }
    }
    if(u == v) return u;
    for(int i = D - 1; i >= 0; --i) {
        if(dp[u][i] != dp[v][i]) {
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[u][0];
}

int add[maxm<<2];

void bulid(int l, int r, int rt) {
    add[rt] = 0;
    if(l == r) return ;
    int m = (l + r) >> 1;
    bulid(l, m, rt<<1);
    bulid(m + 1, r, rt<<1|1);
    return ;
}

void push_down(int rt) {
    if(add[rt]) {
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        add[rt] = 0;
    }
    return ;
}

void update(int L, int R, int l, int r, int rt, int c) {
    if(L == l && R == r) {
        add[rt] += c;
        return ;
    }
    push_down(rt);
    int m = (l + r) >> 1;
    if(R <= m) {
        update(L, R, l, m, rt<<1, c);
    } else if(L > m) {
        update(L, R, m + 1, r, rt<<1|1, c);
    } else {
        update(L, m, l, m, rt<<1, c);
        update(m + 1, R, m + 1, r, rt<<1|1, c);
    }
    return ;
}

int query(int L, int R, int l, int r, int rt) {
    if(L == l && R == r) {
        return add[rt];
    }
    push_down(rt);
    int m = (l + r) >> 1;
    if(R <= m) {
        return query(L, R, l, m, rt<<1);
    } else if(L > m) {
        return query(L, R, m + 1, r, rt<<1|1);
    } else {
        return query(L, m, l, m, rt<<1) + query(m + 1, R, m + 1, r, rt<<1|1);
    }
}

int main() {

    //freopen("aa.in", "r", stdin);

    int k, u, v, w;
    while(scanf("%d %d %d", &N, &Q, &S) != EOF) {
        init_graph();
        for(int i = 1; i < N; ++i) {
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }
        dis[1] = dep[1] = 0;
        dfs(1, 1);
        bulid(1, 2*N, 1);
        for(int i = 0; i < Q; ++i) {
            scanf("%d", &k);
            if(k == 0) {
                scanf("%d", &u);
                int l = lca(S, u);
                int d1 = dis[S] + query(first[S], first[S], 1, 2*N, 1);
                int d2 = dis[u] + query(first[u], first[u], 1, 2*N, 1);
                int d3 = dis[l] + query(first[l], first[l], 1, 2*N, 1);
                printf("%d\n", d1 + d2 - 2 * d3);
                S = u;
            } else {
                scanf("%d %d", &u, &v);
                int t, t_u, t_v;
                t_u = edges[(u-1)<<1].u;
                t_v = edges[(u-1)<<1].v;
                if(dp[t_u][0] == t_v) {
                    t = t_u;
                } else {
                    t = t_v;
                }
                update(first[t], second[t], 1, 2*N, 1, v - edges[(u-1)<<1].w);
                edges[(u-1)<<1].w = v;
                edges[((u-1)<<1)^1].w = v;
            }
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator