Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 树链剖分+线段树+单点更新+拆边

Posted by a280920481 at 2019-07-12 15:58:53 on Problem 2763
```#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 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;
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);
return 0;
}

void add_edge(const int& u, const int& v)
{
}

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: