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+线段树

Posted by sponge_wxy at 2015-05-08 12:01:07 on Problem 2763
```#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];

void init_graph() {
tot = 0;
edge_sum = 0;
}

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].u = v;
edges[edge_sum].v = u;
edges[edge_sum].w = w;
}

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];
}

void bulid(int l, int r, int rt) {
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) {
}
return ;
}

void update(int L, int R, int l, int r, int rt, int c) {
if(L == l && R == r) {
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) {
}
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);
}
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: