| ||||||||||
| 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