SPOJ 375 (트 리 체인 분할 + 선분 트 리)

제목: N 개의 노드 를 포함 하 는 나무 한 그루 는 각 변 에 하나의 가중치 가 있 습 니 다. 두 가지 동작 을 모 의 해 야 합 니 다. (1) 특정한 변 의 가중치 를 바 꾸 고 (2) U, V 사이 의 경로 에서 가중치 가 가장 큰 변 을 물 어보 십시오.
사고: 최근 에 경 기 는 나무 사슬 로 나 누 어 진 문 제 를 보고 논문 을 봤 습 니 다. 이 문 제 를 풀 었 습 니 다. 사고 논문 에서 분명하게 말 했 습 니 다. 오 랜 시간 동안 선분 수 를 쓰 지 않 았 고 여러 번 틀 렸 습 니 다.나 무 를 경중 변 경로 로 나누다.문의 조작 에 대해 우 리 는 두 가지 점 에서 가장 가 까 운 공공 조상 까지 의 경 로 를 각각 처리 할 수 있다.경 로 는 최대 O (log N) 개의 가 벼 운 변 과 O (log N) 개의 무 거 운 경로 로 분해 할 수 있 습 니 다. 그러면 이 두 가지 대상 을 어떻게 유지 하 는 지 고려 해 야 합 니 다.가 벼 운 쪽 에 대해 서 는 우리 가 직접 처리 하면 된다.무 거 운 경로 에 대해 서 는 선분 트 리 로 만 유지 해 야 합 니 다.

#include<stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int N=210000;
const int inf=0x3fffffff;
int son[N],father[N],sz[N],head[N],num,ti[N],idx,dep[N],top[N];
struct edge
{
	int ed,next;
}e[N*3];
struct Edge
{
	int x,y,w;
}E[N*2];
int max(int a,int b)
{
	if(a>b)return a;
	return b;
}
void addedge(int x,int y)
{
	e[num].ed=y;e[num].next=head[x];head[x]=num++;
	e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
//****************************    ***********************
//siz[u]u      
//top[u]u     
//father[u]  u    
//son[u] u          
//ti[u]  u         ，        
void dfs_find(int u,int fa)
{
	int i,v;
	sz[u]=1;dep[u]=dep[fa]+1;son[u]=0;father[u]=fa;
	for(i=head[u];i!=-1;i=e[i].next)
	{
		v=e[i].ed;
		if(v==fa)continue;
		dfs_find(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
}
void dfs_time(int u,int fa)
{
	int i,v;
	ti[u]=idx++;
	top[u]=fa;
	if(son[u]!=0)dfs_time(son[u],top[u]);
	for(i=head[u];i!=-1;i=e[i].next)
	{
		v=e[i].ed;
		if(v==father[u]||v==son[u])continue;
		dfs_time(e[i].ed,e[i].ed);//         
	}
}
//***************************     *************************
struct tree
{
	int L,R,w;
}T[N<<2];
void buildTree(int L,int R,int id)
{
	T[id].L=L;T[id].R=R;T[id].w=-inf;
	if(L==R) return;	 
	int mid=(L+R)>>1;
	buildTree(L,mid,id*2);
	buildTree(mid+1,R,id*2+1);
}
void update(int id,int cp,int w)
{
	if(T[id].L==T[id].R)
	{T[id].w=w;return;}
	int mid=(T[id].L+T[id].R)>>1;
	if(mid>=cp)update(id*2,cp,w);
	else update(id*2+1,cp,w);
	T[id].w=max(T[id*2].w,T[id*2+1].w);
}
int query(int L,int R,int id)
{
	if(T[id].R==R&&T[id].L==L)
		return T[id].w;
	int mid=(T[id].R+T[id].L)>>1;
	if(mid>=R)return query(L,R,id*2);
	else if(mid<L)return query(L,R,id*2+1);
	else	return max(query(L,mid,id*2),query(mid+1,R,id*2+1));
}
int lca(int x,int y)
{
	int ans=-inf;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,query(ti[top[x]],ti[x],1));//x              
		x=father[top[x]];//x          ，       
	}
	if(dep[x]>dep[y])swap(x,y);
	if(x!=y)
		ans=max(ans,query(ti[x]+1,ti[y],1));//ti[x]   x      ，  +1
	return ans;
}
int main()
{
	int i,n,t,x,y,w;
	char str[100];
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		num=0;
		scanf("%d",&n);
		for(i=1;i<n;i++)
		{
			scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);
			addedge(E[i].x,E[i].y);
		}
		dep[1]=0;sz[0]=0;idx=1;
		dfs_find(1,1);
		dfs_time(1,1);
		buildTree(2,n,1);
		for(i=1;i<n;i++)
		{
			if(dep[E[i].x]<dep[E[i].y])
				swap(E[i].x,E[i].y);
			update(1,ti[E[i].x],E[i].w);
		}
		while(true)
		{
			scanf("%s",str);
			if(str[0]=='D')break;
			else if(str[0]=='Q')
			{
				scanf("%d%d",&x,&y);
				printf("%d
",lca(x,y));
			}
			else if(str[0]=='C')
			{
				scanf("%d%d",&i,&w);
				update(1,ti[E[i].x],w);
			}
		}
		printf("
");
	}
	return 0;
}