[나무 사슬 분할] 나무 나무 나무 (POJ 3237)

[제목 배경]
n 개의 결산 점 을 가 진 나 무 를 드 리 겠 습 니 다. 결산 점 번 호 는 1 에서 n 이 고 변 의 번 호 는 1 에서 n - 1 입 니 다.각 변 에 하나의 변 권 이 있다.현재 다음 세 가지 동작 을 모 의 해 야 합 니 다. 1. CHANGE i v: 제 i 조 변 의 가중치 를 v 2. NEGATE a b 로 수정 합 니 다. a 점 에서 b 점 사이 의 경로 의 변 권 을 모두 반대 합 니 다.3. QUERY a b: a 점 에서 b 점 사이 의 경로 의 최대 변 권 을 문의 합 니 다.
[형식 입력]
첫 번 째 행위 의 정수 N (N < = 30000);다음 N - 1 줄 은 각 줄 에 세 개의 정수 a, b, c 를 포함 하고 a 에서 b 까지 한 개의 변 이 있 고 변 권 은 c 임 을 나타 낸다.변 의 번 호 는 입력 한 순서에 따른다.다음은 몇 가지 질문 입 니 다. 한 줄 의 단어 인 'DONE' 를 이 데이터 로 끝 냅 니 다.
[출력 형식]
"QUERY" 마다 한 줄 씩 출력 합 니 다.
변 권 트 리 체인 분할, 최대 치 를 유지 하 는 동시에 최소 치 를 유지 합 니 다. 반 시 최대 치 는 최소 치 와 같 고 최소 치 는 최대 치 와 같 습 니 다.
표 시 를 덮어 쓸 때 표 시 를 직접 전달 하지 마 십시오. 자체 적 으로 표 시 를 가 져 올 수 있 기 때문에 표 시 를 취소 하 는 것 과 같 습 니 다.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int ans,n,h[30005],cnt,prt[30005],deep[30005],size[30005],son[30005],top[30005],seg[30005],rev[30005],a[30005],tag[30005];
struct Tree
{
	int maxx,minn;
}tree[120005];
struct edge
{
	int to,next,v;
}w[60005];
struct que
{
	int x,y,v;
}e[60005];
void add(int x,int y,int z)
{
	cnt++;
	w[cnt].to=y;
	w[cnt].v=z;
	w[cnt].next=h[x];
	h[x]=cnt;
}
void dfs(int x,int fa)
{
	size[x]=1;
	prt[x]=fa;
	deep[x]=deep[fa]+1;
	for(int i=h[x];i;i=w[i].next)
	{
		int to=w[i].to;
		if(to==fa) continue;
		dfs(to,x);
		a[to]=w[i].v;
		size[x]+=size[to];
		if(size[to]>size[son[x]]) son[x]=to;
	}
}
void dfs2(int x,int fa)
{
	seg[x]=++seg[0];
	top[x]=fa;
	if(son[x]) dfs2(son[x],top[x]);
	for(int i=h[x];i;i=w[i].next)
	{
		int to=w[i].to;
		if(top[to]) continue;
		dfs2(to,to);
	}
}
void pushdown(int k)
{
	int maxx=tree[k<<1].maxx;
	tree[k<<1].maxx=-tree[k<<1].minn;
	tree[k<<1].minn=-maxx;
	tag[k<<1]=tag[k]-tag[k<<1];
	maxx=tree[k<<1|1].maxx;
	tree[k<<1|1].maxx=-tree[k<<1|1].minn;
	tree[k<<1|1].minn=-maxx;
	tag[k<<1|1]=tag[k]-tag[k<<1|1];
	tag[k]=0;
}
void update(int k,int l,int r,int ql,int qr)
{
//	cout<>1;
	if(ql<=mid) update(k<<1,l,mid,ql,qr);
	if(middeep[y]) swap(x,y);
	update(1,1,seg[0],seg[son[x]],seg[y]);
}
void change(int k,int l,int r,int x,int v)
{
	if(l==r)
	{
		tree[k].maxx=tree[k].minn=v;
		return ;
	}
	int mid=(l+r)>>1;
	if(tag[k]) pushdown(k);
	if(x<=mid) change(k<<1,l,mid,x,v);
	else change(k<<1|1,mid+1,r,x,v);
	tree[k].maxx=max(tree[k<<1].maxx,tree[k<<1|1].maxx);
	tree[k].minn=min(tree[k<<1].minn,tree[k<<1|1].minn);
}
void query(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
	{
		ans=max(ans,tree[k].maxx);
		return ;
	}
	int mid=(l+r)>>1;
	if(tag[k]) pushdown(k);
	if(ql<=mid) query(k<<1,l,mid,ql,qr);
	if(middeep[y]) swap(x,y);
//	cout<deep[ny]) swap(nx,ny);
		change(1,1,seg[0],seg[ny],e[i].v);
	}
	char s[10];
	while(scanf("%s",s))
	{
		if(s[0]=='D') break;
		int x,y;
		scanf("%d%d",&x,&y);
		if(s[0]=='Q')
		{
			ask(x,y);
			printf("%d
",ans);
		}
		else if(s[0]=='N')
		{
			uprange(x,y);
		}
		else
		{
			int nx=e[x].x,ny=e[x].y;
			if(prt[nx]==ny) change(1,1,seg[0],seg[nx],y);
			else change(1,1,seg[0],seg[ny],y);
		}
	}
}