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

## LCA ----> RMQ

Posted by lz1 at 2011-07-31 19:56:00 on Problem 2763
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <stack>
using namespace std;

#define MAX_N 100005
#define MAX_M 200005

struct node
{
int t, next, len;
node (int _t = 0, int _next = -1, int _len = 0)
{
t = _t, next = _next, len = _len;
}
};

node tree[MAX_M];
int tf[MAX_N], st[MAX_N], en[MAX_N];

int ord[MAX_M], first[MAX_N], dep[MAX_M], dist[MAX_N];
int f[MAX_M][19], logn[MAX_M];// logn[i]: log (2, i)
int fa[MAX_N], x[MAX_N], y[MAX_N], len[MAX_N];
int num, nft, tot;

inline void add(int a, int b, int c)
{
tot++;
tree[tot] = node (b, tf[a], c);
tf[a] = tot;
}

void dfs(int v, int deep)
{
ord[++num] = v, dep[num] = deep, first[v] = num;
st[v] = ++nft;
for (int i = tf[v]; i != -1; i = tree[i].next)
{
if (!first[tree[i].t])
{
dist[tree[i].t] = dist[v] + tree[i].len;
fa[tree[i].t] = v;
dfs (tree[i].t, deep + 1);
ord[++num] = v, dep[num] = deep;
}
}
en[v] = nft;
}

void RMQ_LCA(void)
{
logn[0] = -1;
for (int i = 1; i <= num; i++)
f[i][0] = i;
for (int j = 1, s = 1; s <= num; s <<= 1, j++)
{
for (int i = 1; i + s<= num; i++)
{
if (dep[f[i][j - 1]] < dep[f[i + s][j - 1]])
f[i][j] = f[i][j - 1];
else f[i][j] = f[i + s][j - 1];
}
}
}

int LCA(int a, int b)
{
a = first[a], b = first[b];
if (a > b) swap (a, b);
int k = logn[b - a + 1], s = 1 << k;
if (dep[f[a][k]] < dep[f[b - s + 1][k]])
return ord[f[a][k]];
else return ord[f[b - s + 1][k]];
}

int sum[MAX_N * 3];
int n, m, q, now;
int sl, sr, dt;

inline void down(int root)
{
sum[root * 2] += sum[root],
sum[root * 2 + 1] += sum[root],
sum[root] = 0;
}

void insert (int l, int r, int idx)
{
if (sr < l || sl > r) return ;
if (sl <= l && r <= sr)
{
sum[idx] += dt;
return ;
}
down (idx);
int mid = (l + r) >> 1;
if (sr <= l) insert (l, mid, idx << 1);
else
{
insert (l, mid, idx << 1);
insert (mid + 1, r, (idx << 1) + 1);
}
}

int query (int l, int r, int idx)
{
if (l == r) return sum[idx];
down (idx);
int mid = (l + r) >> 1;
if (sl <= mid) return  query (l, mid, idx << 1) ;
else return query (mid + 1, r, (idx << 1) + 1);
}

int main(void)
{
scanf("%d%d%d", &n, &m, &now);
logn[0] = -1;
for (int i = 1; i < MAX_M; i++)
logn[i] = (i & (i - 1)) ? logn[i - 1]: logn[i - 1] + 1;
memset (tf, -1, sizeof (tf));
for (int i = 1; i < n; i++)
{
scanf ("%d%d%d", x + i, y + i, len + i);
}
dfs (1 ,0);
RMQ_LCA();
for (int i = 1, sign, t, w; i <= m; i++)
{
scanf ("%d", &sign);
if (sign == 1)
{
scanf ("%d%d", &t, &w);
dt = w - len[t], len[t] = w;
if (fa[x[t]] == y[t]) t = x[t];
else t = y[t];
sl = st[t], sr = en[t];
insert (1, n, 1);
}
else
{
scanf ("%d", &t);
int lca = LCA (now, t), p;
sl = st[now], p = dist[now] + query (1, n, 1);
sl = st[t], p += dist[t] + query (1, n, 1);
sl = st[lca], p -= 2 * (dist[lca] + query (1, n, 1));
printf ("%d\n", p);
now = t;
}
}
return 0;
}

```

Followed by: