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 |
树链剖分+线段树+单点更新+拆边#include <algorithm> using namespace std; const int MAX_N = 200008; struct Edge { int to; int next; Edge(const int& to, const int& next) :to(to), next(next) {} Edge() :to(-1), next(-1) {} }G[2 * MAX_N]; int head[MAX_N]; int deg; int cnt; int par[MAX_N]; int depth[MAX_N]; int scnt[MAX_N]; int rk[MAX_N]; int top[MAX_N]; int id[MAX_N]; int son[MAX_N]; int init_t(const int n); void add_edge(const int& u, const int& v); void dfs1(const int v); void dfs2(const int v, const int tp); int _n; int dat[1 << 19]; void init(const int n); int query(const int& left, const int& right, const int k, const int begin, const int end); void update(int p, const int& x); int query(int x, int y); int A[MAX_N]; int main() { int n, q, s, a, b, w, op; scanf("%d%d%d", &n, &q, &s); --s; int ecnt = n; const int n2 = 2 * n - 1; init_t(n2); for (int i = 1; i < n; ++i) { scanf("%d%d%d", &a, &b, &w); --a; --b; add_edge(a, ecnt); add_edge(ecnt, b); A[ecnt++] = w; } int root = 0; dfs1(root); dfs2(root, root); init(n2); while (q--) { scanf("%d%d", &op, &a); --a; if (op) { scanf("%d", &w); update(id[n + a], w); } else { printf("%d\n", query(s, a)); s = a; } } return 0; } int init_t(const int n) { par[0] = deg = cnt = 0; fill(son, son + n + 1, -1); fill(head, head + n + 1, -1); return 0; } void add_edge(const int& u, const int& v) { G[deg] = Edge(v, head[u]); head[u] = deg++; G[deg] = Edge(u, head[v]); head[v] = deg++; } void dfs1(const int v) { scnt[v] = 1; depth[v] = depth[par[v]] + 1; int maxson = -1; for (int i = head[v]; ~i; i = G[i].next) { const int& to = G[i].to; if (to != par[v]) { par[to] = v; dfs1(to); scnt[v] += scnt[to]; if (scnt[to] > maxson) { maxson = scnt[to]; son[v] = to; } } } } void dfs2(const int v, const int tp) { top[v] = tp; id[v] = cnt; rk[cnt++] = v; if (~son[v]) { dfs2(son[v], tp); for (int i = head[v]; ~i; i = G[i].next) { const int& to = G[i].to; if (to != par[v] && to != son[v]) { dfs2(to, to); } } } } void init(const int n) { _n = 1; while (_n < n) { _n <<= 1; } --_n; for (int i = 0; i < n; ++i) { dat[_n + i] = A[rk[i]]; } for (int i = _n - 1; i >= 0; --i) { dat[i] = dat[(i << 1) + 1] + dat[(i << 1) + 2]; } } int query(const int& left, const int& right, const int k, const int begin, const int end) { if (left <= begin && end <= right) { return dat[k]; } else if (left <= end && begin <= right) { return query(left, right, (k << 1) + 1, begin, (begin + end) >> 1) + query(left, right, (k << 1) + 2, ((begin + end) >> 1) + 1, end); } else return 0; } void update(int p, const int& x) { p += _n; int d = x - dat[p]; dat[p] = x; while (p) { p = (p - 1) >> 1; dat[p] += d; } } int query(int x, int y) { int s = 0; while (top[x] != top[y]) { if (depth[top[x]] < depth[top[y]]) { swap(x, y); } s += query(id[top[x]], id[x], 0, 0, _n); x = par[top[x]]; } if (id[x] < id[y]) { swap(x, y); } s += query(id[y], id[x], 0, 0, _n); return s; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator