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

NO IMAGE

傳送門
題目大意:

知道了一顆有 n 個節點的樹和樹上每條邊的權值,對應兩種操作:
0 x 輸出 當前節點到 x節點的最短距離,並移動到 x 節點位置
1 x val 把第 x 條邊的權值改為 val

思路:

樹上兩個節點a,b的距離可以轉化為 dis[a] dis[b] – 2*dis[lca(a,b)]
其中 dis[i] 表示 i 節點到根的距離,
由於每次修改一條邊,樹中在這條邊下方的 dis[] 值全都會受到影響,這樣每條邊都對應這一段這條邊的管轄區,
可以深搜儲存遍歷該點的時間戳,p1[i] 表示第一次遍歷到該點的時間戳, p2[i] 表示回溯到該點時的時間戳,這樣每次
修改邊 i 的時候就可以對區間 [ p1[i], p2[i] ] 進行成段更新,成段更新的方式可以在 位置 p1[i] 上加一個權值,在位置
p2[i] 1 上減去這個權值,求和時,sum( p1[i] ) 即為該點到根的距離

AC Code

const int maxn = 1e5 5;
int c[maxn], p1[maxn], p2[maxn];
int cnt, head[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};
head[u] = cnt  ;
}
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;
add(u, v, w, i); add(v, u, w, i);
}
dfs_id(1, -1); dfs(1, -1, 0);
for (int i = 1 ; i < n ; i   ) {
add(p1[id[i]], a[i]); add(p2[id[i]] 1, -a[i]);
}
while(q--) {
int op, t, g;
scanf("%d", &op);
if (op) {
scanf("%d%d", &t, &g);
int tmp = a[t]; a[t] = g;
add(p1[id[t]], g-tmp); add(p2[id[t]] 1, tmp-g);
}
else {
int t; scanf("%d", &t);
printf("%d\n", getsum(p1[st])   getsum(p1[t]) - 2*getsum(p1[LCA_BZ(st, t)]));
st = t;
}
}
}

當然也可以用樹鏈剖分做, 這樣做的話這就是個裸題了….