SPOJ 375 Query on a tree 樹鍊剖分入門題



http://www.spoj.com/problems/QTREE/

375. Query on a tree

Problem code: QTREE

You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

We will ask you to perfrom some instructions of the following form:

• CHANGE i ti : change the cost of the i-th edge to ti

  or

• QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000),
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integersa b c denotes an edge betweena,b of costc (c <= 1000000),
• The next lines contain instructions "CHANGE i ti" or "QUERY a b",
• The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

Output

For each "QUERY" operation, write one integer representing its result.

Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3
      

題意：給一棵n個節點的樹，有兩種操作，一種是查詢第從a到b路徑上權值最大的邊權，一種是修改第i條邊的值。

關于樹鍊剖分:http://blog.sina.com.cn/s/blog_7a1746820100wp67.html

将這棵樹樹鍊剖分轉化成線性的，修改邊權改為修改該邊結尾的點的點權，就成了線段樹動态求最大值了。每個操作都是logn的。

/**
 * @author neko01
 */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define clr(a) memset(a,0,sizeof a)
#define clr1(a) memset(a,-1,sizeof a)
#define dbg(a) printf("%d\n",a)
typedef pair<int,int> pp;
const double eps=1e-9;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
const int N=10005;
struct edge{
	int to,next;
}e[N*2];
int head[N],tot;
int top[N]; //top[v]表示v所在的鍊的頂端節點
int fa[N];  //fa[v]表示v的父親
int dep[N]; //dep[v]表示v的深度
int num[N]; //num[v]表示以v為根的子樹的節點數
int son[N]; //son[v]表示v的重兒子
int p[N];   //p[v]表示v與其父親節點的連邊線上段樹中的位置
int pos;
int a[N][3];
void init()
{
	tot=0;
	clr1(head);
	clr1(son);
	pos=0;
}
void add(int u,int v)
{
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot++;
}
void dfs1(int u,int pre,int d)  //第一次dfs求出fa,deep,num,son找重邊
{
	num[u]=1;
	fa[u]=pre;
	dep[u]=d;
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=pre)
		{
			dfs1(v,u,d+1);
			num[u]+=num[v];
			if(son[u]==-1||num[v]>num[son[u]])
				son[u]=v;
		}
	}
}
void dfs2(int u,int sp)  //第二次dfs連重邊成重鍊,求出top和p數組
{
	top[u]=sp;
	p[u]=pos++;
	if(son[u]!=-1)
		dfs2(son[u],sp);
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=son[u]&&v!=fa[u])
			dfs2(v,v);
	}
}
struct node{
	int l,r;
	int Max;
}tree[N*4];
void build(int x,int l,int r)
{
	tree[x].l=l;
	tree[x].r=r;
	tree[x].Max=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void update(int x,int k,int val)  //更改線段樹的第k個數為val
{
	if(tree[x].l==k&&tree[x].r==k)
	{
		tree[x].Max=val;
		return;
	}
	int mid=(tree[x].l+tree[x].r)>>1;
	if(k<=mid) update(x<<1,k,val);
	else update(x<<1|1,k,val);
	tree[x].Max=max(tree[x<<1].Max,tree[x<<1|1].Max);  //push up
}
int query(int x,int l,int r)  //查詢線段樹l到r最大值
{
	if(tree[x].l==l&&tree[x].r==r)
		return tree[x].Max;
	int mid=(tree[x].l+tree[x].r)>>1;
	if(r<=mid) return query(x<<1,l,r);
	else if(l>mid) return query(x<<1|1,l,r);
	else return max(query(x<<1,l,mid),query(x<<1|1,mid+1,r));
}
int getmax(int u,int v)   //查詢u到v路徑上的最大值
{
    int f1=top[u],f2=top[v];
    int ans=0;
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])
        {
            swap(f1,f2);
            swap(u,v);
        }
        ans=max(ans,query(1,p[f1],p[u]));
        u=fa[f1];
        f1=top[u];
    }
    if(u==v) return ans;
    if(dep[u]>dep[v]) swap(u,v);
    return max(ans,query(1,p[son[u]],p[v]));
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
	    int n;
		scanf("%d",&n);
		init();
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
			add(a[i][0],a[i][1]);
			add(a[i][1],a[i][0]);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		build(1,0,pos-1);
		for(int i=1;i<n;i++)
        {
            if(dep[a[i][0]]>dep[a[i][1]])
                swap(a[i][0],a[i][1]);
            update(1,p[a[i][1]],a[i][2]);
        }
		char s[10];
		while(~scanf("%s",s))
        {
            if(s[0]=='D') break;
            int u,v;
            scanf("%d%d",&u,&v);
            if(s[0]=='C')
                update(1,p[a[u][1]],v);
            else
                printf("%d\n",getmax(u,v));
        }
	}
	return 0;
}