treeset底層，SPOJ 375 Query on a tree（線段樹維護樹鏈剖分）

題目鏈接：http://www.spoj.com/problems/QTREE/

題意：給出一個樹，兩種操作：（1）修改某條邊的權值；（2）詢問某兩個頂點之間邊的最大值。

思路：樹的路徑剖分和線段樹維護路徑剖分。

（1）輕邊和重邊：記Size(U)表示以U為根的子樹的結點個數。令V為U的兒子中Size(V)最大的一個，那么我們稱邊(U，V)為重邊，其余邊為輕邊。

treeset底層、

如上圖，粗邊為重邊，細邊為輕邊。

（2）樹鏈：將所有的重邊連起來得到若干條鏈，這些鏈叫做樹鏈。上圖中紅點標記的點為每條樹鏈的頭。單獨一個節點自己組成一個樹鏈。

（3）下面我們講如何得到樹鏈。步驟是進行兩次DFS，第一次DFS，得到如下數組：dep[u]u的深度，son[u]<u,son[u]>為重邊,father[u]u的父節點。第二次DFS建立樹鏈，得到如下數組：w[u]:<father[u],u>這條邊在線段樹中的位置為w[u]。如上圖所示，一條樹鏈中的邊在線段樹中是連續的一段，top[u]u在樹鏈中的頭，上圖中top[1]=top[4]=top[9]=top[13]=top[14]=1,top[2]=top[6]=top[11]=2。

（4）單點操作：比如題目中的第一種操作。這種操作比較簡單，直接在線段樹中找到這個點直接更新即可。

java線段樹，（5）成段操作：比如成段更新或查詢等。我們拿10和11作為例子說明。首先，我們得到u=10和v=11的top值，分別是f1=10和f2=2，發現f1的dep值大，則更新圖中的邊5；接著u=4,f1=1，此時f2的深度的，則更新圖中的邊9、10和11，接著v=1,f1=1，退出。

有了這些，本題就比較容易了。

?

vector<int> g[N];
int dep[N],w[N],father[N],top[N],son[N],size[N];
int E[N][3],root,n,z;
int tree[N<<2];


void DFS1(int u)
{
? ? size[u]=1; son[u]=0;
? ? int i,v;
? ? FOR0(i,SZ(g[u]))
? ? {
? ? ? ? v=g[u][i];
? ? ? ? if(v==father[u]) continue;
? ? ? ? father[v]=u;
? ? ? ? dep[v]=dep[u]+1;
? ? ? ? DFS1(v);
? ? ? ? if(size[v]>size[son[u]]) son[u]=v;
? ? ? ? size[u]+=size[v];
? ? }
}


void DFS2(int u,int root)
{
? ? w[u]=++z; top[u]=root;
? ? if(son[u]) DFS2(son[u],root);
? ? int i,v;
? ? FOR0(i,SZ(g[u]))
? ? {
? ? ? ? v=g[u][i];
? ? ? ? if(v!=son[u]&&v!=father[u]) DFS2(v,v);
? ? }
}


void build(int t,int L,int R,int pos,int x)
{
? ? if(L==R)
? ? {
? ? ? ? tree[t]=x;
? ? ? ? return;
? ? }
? ? int mid=(L+R)>>1;
? ? if(pos<=mid) build(t*2,L,mid,pos,x);
? ? else build(t*2+1,mid+1,R,pos,x);
? ? tree[t]=max(tree[t*2],tree[t*2+1]);
}


int get(int t,int L,int R,int l,int r)
{
? ? if(L==l&&R==r) return tree[t];
? ? int mid=(L+R)>>1;
? ? if(r<=mid) return get(t*2,L,mid,l,r);
? ? if(l>mid) return get(t*2+1,mid+1,R,l,r);
? ? int x=get(t*2,L,mid,l,mid);
? ? int y=get(t*2+1,mid+1,R,mid+1,r);
? ? return max(x,y);
}


int query(int a,int b)
{
? ? int f1=top[a],f2=top[b],ans=0,temp;
? ? while(f1!=f2)
? ? {
? ? ? ? if(dep[f1]<dep[f2]) swap(f1,f2),swap(a,b);
? ? ? ? temp=get(1,1,z,w[f1],w[a]);
? ? ? ? if(temp>ans) ans=temp;
? ? ? ? a=father[f1];
? ? ? ? f1=top[a];
? ? }
? ? if(a==b) return ans;
? ? if(dep[a]>dep[b]) swap(a,b);
? ? temp=get(1,1,z,w[son[a]],w[b]);
? ? if(temp>ans) ans=temp;
? ? return ans;
}


int main()
{
? ? rush()
? ? {
? ? ? ? RD(n); root=(n+1)>>1; father[root]=0; z=0; dep[root]=0;
? ? ? ? int i;
? ? ? ? FOR1(i,n) g[i].clear();
? ? ? ? FOR1(i,n-1)
? ? ? ? {
? ? ? ? ? ? RD(E[i][0],E[i][1],E[i][2]);
? ? ? ? ? ? g[E[i][0]].pb(E[i][1]);
? ? ? ? ? ? g[E[i][1]].pb(E[i][0]);
? ? ? ? }
? ? ? ? DFS1(root); DFS2(root,root);
? ? ? ? FOR1(i,n-1)
? ? ? ? {
? ? ? ? ? ? if(dep[E[i][0]]>dep[E[i][1]]) swap(E[i][0],E[i][1]);
? ? ? ? ? ? build(1,1,z,w[E[i][1]],E[i][2]);
? ? ? ? }
? ? ? ? char op[10];
? ? ? ? int x,y;
? ? ? ? while(RD(op),op[0]!='D')
? ? ? ? {
? ? ? ? ? ? RD(x,y);
? ? ? ? ? ? if(op[0]=='Q') PR(query(x,y));
? ? ? ? ? ? else build(1,1,z,w[E[x][1]],y);
? ? ? ? }
? ? }
}