poj 3237 강화 판 query on a tree 체인 분할

링크:
http://www.spoj.pl/problems/QTREE/
http://poj.org/problem?id=3237
제목: 나무 한 그루, 두 가지 업데이트 작업, 한 변 의 변 권 을 바 꾸 고 a - > b 경로 의 모든 변 권 을 반대 하 며 한 경로 의 최대 변 권 을 물 습 니 다.
모두 전형 적 인 나무 사슬 로 나 뉘 는데 다음 문 제 는 위의 강화 판 이 고 나무 위 에서 세그먼트 업 데 이 트 를 해 야 하 는데 어렵 지 않다.
다만 구간 에 최소 치 를 하나 더 기록 해 야 한다. 왜냐하면 역작 동 을 취하 면 구간 의 최대 치 와 최소 치 를 교환 할 수 있 기 때문이다.
그 다음 에 나무 사슬 을 나 누 는 낡은 방식 이다. 만약 에 무 거 운 체인 이 라면 온라인 트 리 에서 업데이트 되 고 그렇지 않 으 면 변 권 을 직접 바 꾸 는 것 이다.
선분 나무 에 게 으 름 표 시 를 내 려 놓 을 때 새 서 오래 조정 해서 멘 붕 이 터 졌 습 니 다....................................................
동적 트 리 로 도 가능 할 것 같 아 요. 개념 은 다 알 아 봤 는데 실천 해 본 적 이 없어 요. 다음 에 배 워 서 붙 여 주세요.
다음은 이 두 문제 의 코드 입 니 다. 제 코드 는 좀 비비 고 있 습 니 다. 눈 이 다 치지 않도록 조심 하 세 요 * *
spoj  375  query on a tree

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 20010;
const int inf = ~0u>>2;
int M[maxn<<2];
struct node{
    int s,t,w,next;
}edge[maxn*2];
int E,n;
int size[maxn] , fa[maxn] , heavy[maxn] , head[maxn] , dep[maxn] , rev[maxn] , num[maxn] , cost[maxn];
int Seg_size;
inline void Max(int &x,int y){if(x<y) x=y;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add_edge(int s,int t,int w)
{
    edge[E].w=w;
    edge[E].s=s;
    edge[E].t=t;
    edge[E].next=head[s];
    head[s]=E++;
}
void dfs(int u,int f)
{
    int mx=-1,e=-1;
    size[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].t;
        if(v==f) continue;
        dep[v]=dep[u]+1;
        rev[v]=i^1;
        dfs(v,u);
        size[u]+=size[v];
        if(size[v]>mx)
        {
            mx=size[v];
            e=i;
        }
    }
    heavy[u]=e;
    if(e!=-1)  fa[edge[e].t]=u;
}
inline void pushup(int rt){
    M[rt]=max(M[rt<<1],M[rt<<1|1]);
}
void build(int l,int r,int rt){
    M[rt]=inf;
    if(l==r){
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int p,int val,int l,int r,int rt){
    if(l==r){
       M[rt]=val;
       return ;
    }
    int m=(l+r)>>1;
    if(p<=m) update(p,val,lson);
    else update(p,val,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return M[rt];
    }
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m) ret=max(ret,query(L,R,lson));
    if(R>m) ret=max(ret,query(L,R,rson));
    return ret;
}
void prepare()
{
    build(1,n-1,1);
    memset(num,-1,sizeof(num));
    dep[0]=0;Seg_size=0;
    for(int i=0;i<n;i++) fa[i]=i;
    dfs(0,0);    
    for(int i=0;i<n;i++)
    {
        if(heavy[i]==-1)
        {
            int pos=i;
            while(pos && edge[heavy[edge[rev[pos]].t]].t == pos)
            {
                int t=rev[pos];
                num[t]=num[t^1]=++Seg_size;
                update(Seg_size,edge[t].w,1,n-1,1);
                pos=edge[t].t;
            }
        }
    }
}
void change(int edge_id,int val)
{
    if(num[edge_id]==-1) edge[edge_id].w=edge[edge_id^1].w=val;
    else update(num[edge_id],val,1,n-1,1);
}
int calc(int u,int lca)
{
    int ans=-inf;int vi=0;
    while(u!=lca)
    {
        vi++;
        if(vi==10) break;
        int r=rev[u];
        if(num[r]==-1) Max(ans,edge[r].w),u=edge[r].t;
        else 
        {
            int p=fa[u];
            if(dep[p] < dep[lca]) p=lca;
            int l=num[r];
            int r=num[heavy[p]];
            Max(ans,query(l,r,1,n-1,1));
            u=p;
        }
    }
    return ans;
}
int lca(int u,int v)
{
    while(1)
    {
        int a=find(u),b=find(v);
        if(a==b) return dep[u] < dep[v] ? u : v;//a,b       
        else if(dep[a]>=dep[b]) u=edge[rev[a]].t;
        else v=edge[rev[b]].t;
    }
}
int solve(int u,int v)
{
    int p=lca(u,v);
    return max(calc(u,p),calc(v,p));
}
int main()
{
    int t,i,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        memset(head,-1,sizeof(head));
        E=0;
        scanf("%d",&n);
        for(i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&a,&b,&c);a--;b--;
            add_edge(a,b,c);
            add_edge(b,a,c);
        }
        prepare();
        char op[20];
        while(scanf("%s",op)!=EOF && strcmp(op,"DONE"))
        {
            if(op[0]=='C')
            {
                scanf("%d%d",&a,&c);
                change((a-1)*2,c);
            }
            else 
            {
                scanf("%d%d",&a,&b);
                printf("%d
",solve(a-1,b-1));
            }
        }
    }
    return 0;
}
/*
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
1
3
1
7
1 2 1
1 3 2
2 4 3
2 5 4
3 6 5
3 7 6
Query 1 7
*/

poj 3237

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 100010;
const int inf = ~0u>>2;
int M[maxn<<2];
int Mi[maxn<<2];
int col[maxn<<2];
struct node{
	int s,t,w,next;
}edge[maxn*2];
int E,n;
int size[maxn] , fa[maxn] , heavy[maxn] , head[maxn] , dep[maxn] , rev[maxn] , num[maxn] , cost[maxn];
int Seg_size;
inline void Max(int &x,int y){if(x<y) x=y;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a>b?b:a;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add_edge(int s,int t,int w){
	edge[E].w=w;
	edge[E].s=s;
	edge[E].t=t;
	edge[E].next=head[s];
	head[s]=E++;
}
void dfs(int u,int f){
	int mx=-1,e=-1;
	size[u]=1;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].t;
		if(v==f) continue;
		dep[v]=dep[u]+1;
		rev[v]=i^1;
		dfs(v,u);
		size[u]+=size[v];
		if(size[v]>mx){
			mx=size[v];
			e=i;
		}
	}
	heavy[u]=e;
	if(e!=-1)  fa[edge[e].t]=u;
}
void build(int l,int r,int rt){
	Mi[rt]=inf;
	M[rt]=-inf;
	col[rt]=0;
	if(l==r){
		return ;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
}
inline void pushup(int rt){
	M[rt]=max(M[rt<<1],M[rt<<1|1]);
	Mi[rt]=min(Mi[rt<<1],Mi[rt<<1|1]);
}
void make(int rt){
	int tmp=Mi[rt];
	Mi[rt]=-M[rt];
	M[rt]=-tmp;
}
void pushdown(int rt){
	if(col[rt]){
       col[rt<<1]^=1;
	   make(rt<<1);
	   col[rt<<1|1]^=1;
	   make(rt<<1|1);
	   col[rt]=0;//       ，      ， 
	}
}
void update(int p,int val,int l,int r,int rt){
	if(l==r){
	   Mi[rt]=M[rt]=val;
	   return ;
	}
	pushdown(rt);
	int m=(l+r)>>1;
	if(p<=m) update(p,val,lson);
	else update(p,val,rson);
	pushup(rt);
}
void justdoit(int L,int R,int l,int r,int rt){
	//printf("L=%d R=%d l=%d r=%d
",L,R,l,r);
	if(L<=l&&r<=R){
		col[rt]^=1;
		make(rt);
		return ;
	}
	pushdown(rt);
	int m=(l+r)>>1;
	if(L<=m) justdoit(L,R,lson);
	if(R>m) justdoit(L,R,rson);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		return M[rt];
	}
	pushdown(rt);
	int m=(l+r)>>1;
	int ret=-inf;
	if(L<=m) ret=max(ret,query(L,R,lson));
	if(R>m) ret=max(ret,query(L,R,rson));
	return ret;
}
void prepare(){
	build(1,n-1,1);
	memset(num,-1,sizeof(num));
	dep[0]=0;Seg_size=0;
	for(int i=0;i<n;i++) fa[i]=i;
	dfs(0,0);	
	for(int i=0;i<n;i++){
		if(heavy[i]==-1)	{
			int pos=i;
			while(pos && edge[heavy[edge[rev[pos]].t]].t == pos)	{
				int t=rev[pos];
				num[t]=num[t^1]=++Seg_size;
				update(Seg_size,edge[t].w,1,n-1,1);
				pos=edge[t].t;
			}
		}
	}
}
void change(int edge_id,int val){
	if(num[edge_id]==-1) edge[edge_id].w=edge[edge_id^1].w=val;
	else update(num[edge_id],val,1,n-1,1);
}
int calc(int u,int lca){
	int ans=-inf;
    while(u!=lca){
		int r=rev[u];
		if(num[r]==-1) Max(ans,edge[r].w),u=edge[r].t;
		else {
			int p=fa[u];
			if(dep[p] < dep[lca]) p=lca;
			int l=num[r];
			int r=num[heavy[p]];
			Max(ans,query(l,r,1,n-1,1));
			u=p;
		}
	}
	return ans;
}
void gao(int u,int lca){
	while(u!=lca){
		int r=rev[u];
		if(num[r]==-1) edge[r].w=edge[r^1].w=-edge[r].w,u=edge[r].t;
		else{
			int p=fa[u];
			if(dep[p] < dep[lca]) p=lca;
			int l=num[r];
			int r=num[heavy[p]];
			//printf("l=%d r=%d
",l,r);
			justdoit(l,r,1,n-1,1);
			u=p;
		}
	}
}
int lca(int u,int v){
	while(1){
		int a=find(u),b=find(v);
		if(a==b) return dep[u] < dep[v] ? u : v;//a,b       
		else if(dep[a]>=dep[b]) u=edge[rev[a]].t;
		else v=edge[rev[b]].t;
	}
}
int solve(int u,int v){
	int p=lca(u,v);
	return max(calc(u,p),calc(v,p));
}
void sol(int u,int v){
	int p=lca(u,v);//printf("p=%d
",p);
	gao(u,p);gao(v,p);
}
int main(){
	int t,i,a,b,c;
	scanf("%d",&t);
	while(t--)	{
		memset(head,-1,sizeof(head));
		E=0;
		scanf("%d",&n);
		for(i=0;i<n-1;i++){
			scanf("%d%d%d",&a,&b,&c);a--;b--;
			add_edge(a,b,c);
			add_edge(b,a,c);
		}
		prepare();
		char op[20];
		while(scanf("%s",op)!=EOF && strcmp(op,"DONE")){
			if(op[0]=='C'){
				scanf("%d%d",&a,&c);
				change((a-1)*2,c);
			}
			else if(op[0]=='N'){
				scanf("%d%d",&a,&b);
				if(a==b) while(1);
				sol(a-1,b-1);
			}
			else {
				
				scanf("%d%d",&a,&b);
				if(a==b) while(1);
				printf("%d
",solve(a-1,b-1));
			}
		}
	}
	return 0;
}