q次詢問求兩個點之間的距離，并且可以隨時修改某條邊的長度，最短距離可以用lca來求，但是樹上維護每一個點到root的距離必須要用dfs序來記錄時間戳，在dfs的時候順便記錄每一條邊（u,v）對應的v節點，更改某條邊時需要更新的是將L[v]~R[v]的值加上這一條邊的變化量，然后log查詢每個點到root的距離即可。

改變這一條邊u->v的值,要記錄v點，因為其實改變這條邊的值改變的是L[v]~R[v]的值

對應的線段樹的操作就是區間更新，單點查詢。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
const int dir[4][2]= {0,-1,-1,0,0,1,1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=1e5+5;
int f[maxn][33],head[maxn],dis[maxn],s[maxn],d[maxn];///d表示深度，dis和s是dfs過程中暫時記錄到root點的距離
int L[maxn],R[maxn];///L,R分別記錄dfs序的時間戳，
int way[maxn],eg[maxn];///記錄邊對應dfs中開始的點以及那條邊的權值，eg一直在更新
int root,sign,t,n,q;
struct node
{int to,p,val;
}edge[maxn<<1];
int tree[maxn<<2],lazy[maxn<<2];
void init()
{sign=t=0;for(int i=0;i<=n;i++)head[i]=-1;
}
void add(int u,int v,int val)
{edge[sign].to=v;edge[sign].val=val;edge[sign].p=head[u];head[u]=sign++;
}
void dfs(int u)
{L[u]=++t;s[t]=dis[u];for(int i=1;(1<<i)<=n;i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=head[u];~i;i=edge[i].p){int v=edge[i].to;if(f[u][0]==v) continue;dis[v]=dis[u]+edge[i].val;way[i/2+1]=v;///這一條邊u->v,記錄v點，因為改變這條邊的值改變的是L[v]~R[v]的值eg[i/2+1]=edge[i].val;///因為改變量，所以更新后要記錄d[v]=d[u]+1;///深度f[v][0]=u;///父親dfs(v);}R[u]=t;
}
void pushdown(int i)
{if(lazy[i]){lazy[lson]+=lazy[i];lazy[rson]+=lazy[i];lazy[i]=0;}
}
void build(int i,int l,int r)
{lazy[i]=0;if(l==r){tree[i]=s[l];return;}int mid=half;build(Lson);build(Rson);
}
void update(int i,int l,int r,int ql,int qr,int val)
{if(ql<=l&&qr>=r){lazy[i]+=val;return;}int mid=half;if(qr<=mid) update(Lson,ql,qr,val);else if(ql>=mid+1) update(Rson,ql,qr,val);else {update(Lson,ql,mid,val);update(Rson,mid+1,qr,val);}
}
int query(int i,int l,int r,int x)
{if(l==r) return tree[i]+lazy[i];int mid=half;pushdown(i);if(x<=mid) return query(Lson,x);else return query(Rson,x);
}
int lca(int a,int b)
{if(d[a]<d[b]) swap(a,b);int x=d[a]-d[b];for(int i=0;(1<<i)<=x;i++)if((1<<i)&x) a=f[a][i];if(a!=b){for(int i=(int)log2(n);i>=0;i--)if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];a=f[a][0];}return a;
}
int find(int a,int b)
{int r=lca(a,b);return query(1,1,n,L[a])+query(1,1,n,L[b])-2*query(1,1,n,L[r]);
}
int main()
{int op,x,y,val;while(cin>>n>>q>>root){init();for(int i=1;i<n;i++){scanf("%d %d %d",&x,&y,&val);add(x,y,val),add(y,x,val);}f[root][0]=root,d[root]=0,dis[root]=0;dfs(root);build(1,1,n);while(q--){scanf("%d",&op);if(!op){scanf("%d",&x);printf("%d\n",find(root,x));root=x;}else{scanf("%d %d",&x,&y);int v=way[x];update(1,1,n,L[v],R[v],y-eg[x]);eg[x]=y;}}}return 0;
}

?

總結

以上是生活随笔為你收集整理的POJ - 2763 Housewife Wind LCA+dfs序+线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。