Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
LCA+线段树#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator