# POJ – 2763 Housewife Wind 【LCA 樹狀陣列 or 樹鏈剖分】

0 x 輸出 當前節點到 x節點的最短距離，並移動到 x 節點位置
1 x val 把第 x 條邊的權值改為 val

p2[i] 1 上減去這個權值，求和時，sum( p1[i] ) 即為該點到根的距離

AC Code

const int maxn = 1e5 5;
int c[maxn], p1[maxn], p2[maxn];
int up[maxn][21], id[maxn];
int deep[maxn], dis[maxn];
int n, q, st, ti;
void add(int i, int x) {
while(i <= n) {
c[i]  = x;
i  = i&(-i);
}
}
int getsum(int i) {
int ans = 0;
while(i) {
ans  = c[i];
i -= i&(-i);
}
return ans;
}
struct node {
int to, next, w, idx;
}e[maxn<<1];
void init() {
ti = 0; cnt = 0; Fill(head, -1); Fill(c, 0);
Fill(up,0); Fill(deep,0); Fill(dis, 0);
}
void add(int u, int v, int w, int idx) {
e[cnt] = {v, head[u], w, idx};
}
void dfs_id(int u, int fa) {
p1[u] =   ti;
for(int i = head[u] ; ~i ; i = e[i].next){
int to = e[i].to;
if(to == fa) continue;
dfs_id(to,u);
}
p2[u] = ti;
}
void dfs(int u,int fa,int d) {
deep[u] = d   1;
for(int i = 1 ; i < 20 ; i   ) {
up[u][i] = up[up[u][i-1]][i-1];
}
for(int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
if(to == fa) continue;
dis[to] = dis[u]   e[i].w;
id[e[i].idx] = e[i].to;
up[to][0] = u;
dfs(to, u, d 1);
}
}
int LCA_BZ(int u,int v) {
int mx = 0;
if(deep[u] < deep[v]) swap(u,v);
int k = deep[u] - deep[v];
for(int i = 0 ; i < 20 ; i   ) {
if((1<<i) & k) {
u = up[u][i];
}
}
if(u != v) {
for(int i = 19 ; i >= 0 ; i --) {
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
u = up[u][0];
}
return u;
}
int a[maxn];
void solve() {
scanf("%d%d%d", &n ,&q, &st);
init();
for (int i = 1 ; i < n ; i   ) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
a[i] = w;
}
dfs_id(1, -1); dfs(1, -1, 0);
for (int i = 1 ; i < n ; i   ) {
}
while(q--) {
int op, t, g;
scanf("%d", &op);
if (op) {
scanf("%d%d", &t, &g);
int tmp = a[t]; a[t] = g;