| ||||||||||
| 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 | |||||||||
LCA+线段树#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];
int head[maxn], edge_sum;
void init_graph() {
tot = 0;
edge_sum = 0;
memset(head, -1, sizeof(head));
}
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].next = head[u];
head[u] = edge_sum++;
edges[edge_sum].u = v;
edges[edge_sum].v = u;
edges[edge_sum].w = w;
edges[edge_sum].next = head[v];
head[v] = edge_sum++;
}
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];
}
int add[maxm<<2];
void bulid(int l, int r, int rt) {
add[rt] = 0;
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) {
if(add[rt]) {
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
add[rt] = 0;
}
return ;
}
void update(int L, int R, int l, int r, int rt, int c) {
if(L == l && R == r) {
add[rt] += c;
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) {
return add[rt];
}
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);
add_edge(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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator