給你一棵樹每條邊的權值，有兩種操作：修改某一條邊的權值；詢問兩點之間的路徑和。（多組數據）
1
3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE
1 3
樹鏈剖分是一種把樹上詢問轉換為鏈狀詢問的方法，也就是說只要是單鏈能做樹上也能做，并且只會加一個很小的常數。所以一般如果部分分是單鏈的話，后面的點肯定能用樹剖做。
預處理時，把一棵樹剖成若干條鏈，然后用單鏈的方式維護。我們把鏈上的邊叫做重邊，重邊與重邊之間的邊叫做輕邊。下圖中粗的邊就是重邊。不過每條鏈單獨維護太復雜，那就直接把所有鏈接在一起維護。 有一個性質：如果按照重邊dfs（比如下圖中1之后訪問4）每條鏈的dfs序編號一定是連續的。詢問時，把每個詢問拆成若干條鏈，在數據結構上查詢。
剖分也有好壞之分。感性的想一想（后面有證明），由于重邊用數據結構維護，復雜度為logn，輕邊直接直接訪問，復雜度為n，那么我們希望每次盡量多的訪問重邊，這里用到一個啟發式剖分。 定義： dep[x] x節點的深度 siz[x] x的子樹大小 fa[x] x的父節點 id[x] x節點的編號（轉換到樹鏈后的編號） son[x] x的重兒子 top[x] x所在重鏈的頂端 重兒子的定義：所有兒子中siz最大的一個 首先dfs一次，找出所有節點的重兒子，同時可以處理出dep、siz、fa；然后再dfs一次，每次優先搜索重兒子，這樣就能向下拉出一條重鏈，回溯的時候，其他非重兒子依次繼續向下拉出一條重鏈。比如上圖中一開始拉出了1、4、9、13、14，然后回溯到1的時候，訪問2，然后2再向下拉出一條重鏈。
void dfs1(int x,int ftr,int d){ dep[x] = d; siz[x] = 1; son[x] = 0; fa[x] = ftr; for (int i = 0;i < v[x].size(); i++) { int nxt = v[x][i]; if (nxt == ftr) continue; dfs1(nxt,x,d+1); siz[x] += siz[nxt]; if (siz[nxt] > siz[son[x]]) son[x] = nxt; }}void dfs2(int x,int tp){ top[x] = tp; id[x] = ++num; if (son[x] > 0) dfs2(son[x],tp); for (int i = 0;i < v[x].size(); i++) { int nxt = v[x][i]; if (nxt == fa[x] || nxt == son[x]) continue; dfs2(nxt,nxt); }}關于這樣的剖分有如下性質： 1、輕邊(u,v)中，size(v)<=size(u/2)。 用反證法顯然。 2、從根到某一點的路徑上，不超過logn條輕邊和不超過logn條重路徑。雖然我不會證這個，但我知道這就保證了『每次盡量多的訪問重邊』。
這里我用的是線段樹維護。之前的剖分做完之后問題完全轉化為單鏈怎么做，那就很簡單了。
下面講講怎么查詢(u,v)。 分成兩種情況考慮： 1、u和v在同一條重鏈上，即top[u] = top[v]，這個時候直接在線段樹里找就好了，因為之前說過u到v的節點是連續的。 2、u和v不在同一條重鏈上。比較兩條鏈的起點，哪個比較低，哪個節點就跑到這條鏈的頂端，此時再向上爬一條邊（輕邊）就來到了一條新的重鏈，然后循環。顯然這個點到頂點也是連續的，而向上爬一層輕邊的時間復雜度僅為o(1)。
int link(int u,int v){ int top1 = top[u]; int top2 = top[v]; int res = 0; while (top1 != top2) { if (dep[top1] < dep[top2]) {swap(top1,top2); swap(u,v);} res = max(query(1,id[top1],id[u]),res); u = fa[top1]; top1 = top[u]; } if (u == v) return res; if (dep[u] > dep[v]) swap(u,v); res = max(query(1,id[son[u]],id[v]),res); return res;}感覺樹剖封裝性比較好。。。大部分時候只要先研究一下單鏈，然后拖個樹剖，改一下link函數里面的查詢操作就行了。
#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 10005using namespace std;struct tree1{ int x,y,val; void read(){scanf("%d%d%d",&x,&y,&val);}} e[N];vector<int> v[N];struct tree2{ int l,r,val;} tree[N*4];int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N];int T,num,i,n,x,y;void dfs1(int x,int ftr,int d){ dep[x] = d; siz[x] = 1; son[x] = 0; fa[x] = ftr; for (int i = 0;i < v[x].size(); i++) { int nxt = v[x][i]; if (nxt == ftr) continue; dfs1(nxt,x,d+1); siz[x] += siz[nxt]; if (siz[nxt] > siz[son[x]]) son[x] = nxt; }}void dfs2(int x,int tp){ top[x] = tp; id[x] = ++num; if (son[x] > 0) dfs2(son[x],tp); for (int i = 0;i < v[x].size(); i++) { int nxt = v[x][i]; if (nxt == fa[x] || nxt == son[x]) continue; dfs2(nxt,nxt); }}void build(int l,int r,int rt){ tree[rt].l = l; tree[rt].r = r; if (l == r) {tree[rt].val = val[l]; return;} int mid = (l + r) >> 1; build(l,mid,rt << 1); build(mid+1,r,rt << 1 | 1); tree[rt].val = max(tree[rt<<1].val,tree[rt<<1|1].val);}void update(int rt,int key,int val){ if (tree[rt].l == tree[rt].r) {tree[rt].val = val; return;} int mid = (tree[rt].l + tree[rt].r) >> 1; if (key <= mid) update(rt<<1,key,val); else update(rt<<1|1,key,val); tree[rt].val = max(tree[rt<<1].val,tree[rt<<1|1].val);}int query(int rt,int l,int r){ if (tree[rt].l >= l && tree[rt].r <= r) return tree[rt].val; int mid = (tree[rt].l + tree[rt].r) >> 1; int res = 0; if (l <= mid) res = max(res,query(rt<<1,l,r)); if (r > mid) res = max(res,query(rt<<1|1,l,r)); return res;}int link(int u,int v){ int top1 = top[u]; int top2 = top[v]; int res = 0; while (top1 != top2) { if (dep[top1] < dep[top2]) {swap(top1,top2); swap(u,v);} res = max(query(1,id[top1],id[u]),res); u = fa[top1]; top1 = top[u]; } if (u == v) return res; if (dep[u] > dep[v]) swap(u,v); res = max(query(1,id[son[u]],id[v]),res); return res;}int main(){ scanf("%d",&T); while (T--) { scanf("%d",&n); for (i = 1;i < n; i++) { e[i].read(); v[e[i].x].push_back(e[i].y); v[e[i].y].push_back(e[i].x); } num = 0; dfs1(1,0,1); dfs2(1,1); for (i = 1;i <= n; i++) { if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x,e[i].y); val[id[e[i].x]] = e[i].val;//val數組用來記錄每個點上面的那條邊的權值 } build(1,n,1); char s[40]; scanf("%s",&s); while (s[0] != 'D') { scanf("%d%d",&x,&y); if (s[0] == 'Q')新聞熱點
疑難解答
