[SPOJ]375.Query on a tree(나무 사슬 분할)

http://www.spoj.com/problems/QTREE/
이것 은 가장자리 에 따라 분류 한 것 이다.
디 버 깅 을 토 할 때 까지 맞 추 지도 못 하고 나중에 데 이 터 를 만 드 는 것 을 고 쳐 서 찍 었 다.멘 붕 아아 아아 아아
디 버 깅 에 시간 이 걸 렸 는데 hld 를 치 는 데 30 분 밖 에 안 걸 렸 어 요.멘 붕.
처음 치면 서 분류 하 는 데 신경 을 안 썼어 요.
바로 fx==fy 이후 x==y 를 판단 하지 않 았 고 그 다음 에 이것 은 분류 하면 서 아버지의 하 표를 얻 었 고 과감하게 틀 렸 다.
멘 붕,이 잘못 을 꼭 기억 해 야 해.

#include <cstring>

#include <cstdio>

#include <iostream>

using namespace std;

#define lc x<<1

#define rc x<<1|1

#define lson l, m, lc

#define rson m+1, r, rc

#define MID (l+r)>>1

#define read(x) x=getint()

#define dbg(x) cout << #x << "=" << x << endl

inline const int max(const int& a, const int& b) { return a>b?a:b; }

inline int getint() { char c; int ret=0, k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }



const int N=50010, oo=~0u>>1;

struct Ed { int u, v, w; }e[N];

int ihead[N], inext[N<<1], to[N<<1], cnt;

int fa[N], sz[N], son[N], top[N], dep[N], id[N], mx[N*5], num[N], tot, L, R, key, n;



inline void pushup(const int &x) { mx[x]=max(mx[lc], mx[rc]); }

void build(const int &l, const int &r, const int &x) {

	if(l==r) { mx[x]=num[l]; return; }

	int m=MID;

	build(lson); build(rson);

	pushup(x); 

}

void update(const int &l, const int &r, const int &x) {

	if(l==r) { mx[x]=key; return; }

	int m=MID;

	if(L<=m) update(lson); if(m<R) update(rson); pushup(x);

}

int getmax(const int &l, const int &r, const int &x) {

	if(L<=l && r<=R) return mx[x];

	int m=MID, ret=oo+1;

	if(L<=m) ret=max(ret, getmax(lson)); if(m<R) ret=max(ret, getmax(rson)); return ret;

}

void dfs1(const int &u) {

	sz[u]=1; int v;

	for(int i=ihead[u]; i; i=inext[i]) if(fa[u]!=(v=to[i])) {

		fa[v]=u; dep[v]=dep[u]+1;

		dfs1(v);

		sz[u]+=sz[v];

		if(sz[v]>sz[son[u]]) son[u]=v;

	}

}

void dfs2(const int &u, const int &tp) {

	id[u]=++tot; top[u]=tp;

	if(son[u]) dfs2(son[u], tp);

	for(int i=ihead[u]; i; i=inext[i]) if(fa[u]!=to[i] && to[i]!=son[u]) dfs2(to[i], to[i]);

}

inline int getmax(int x, int y) {

	int fx=top[x], fy=top[y], ret=oo+1;

	while(fx!=fy) {

		if(dep[fx]<dep[fy]) { swap(x, y); swap(fx, fy); }

		L=id[fx]; R=id[x];

		ret=max(ret, getmax(2, n, 1));

		x=fa[fx]; fx=top[x];

	}

	if(dep[x]>dep[y]) swap(x, y);

	if(x!=y) L=id[x]+1; R=id[y]; //  ，       ，L >R，            

	return max(ret, getmax(2, n, 1));

}

inline void add(const int &u, const int &v) {

	inext[++cnt]=ihead[u]; ihead[u]=cnt; to[cnt]=v;

	inext[++cnt]=ihead[v]; ihead[v]=cnt; to[cnt]=u;

}

int main() {

	int c=getint(), a, b; char ch;

	while(c--) {

		read(n);

		tot=cnt=0;

		memset(ihead, 0, sizeof(int)*(n+10));

		memset(fa, 0, sizeof(int)*(n+10));

		memset(son, 0, sizeof(int)*(n+10));

		for(int i=1; i<n; ++i) {

			read(e[i].u); read(e[i].v); read(e[i].w);

			add(e[i].u, e[i].v);

		}

		dfs1(1); dfs2(1, 1);

		for(int i=1; i<n; ++i) {

			if(dep[e[i].u]>dep[e[i].v]) swap(e[i].u, e[i].v);

			num[id[e[i].v]]=e[i].w;

		}

		build(2, n, 1);

		for(ch=getchar(); ch<'A' || ch>'Z'; ch=getchar());

		while(ch!='D') {

			read(a); read(b);

			if(ch=='C') { key=b; L=R=id[e[a].v]; update(2, n, 1); }

			else printf("%d
", getmax(a, b));

			for(ch=getchar(); ch<'A' || ch>'Z'; ch=getchar());

		}

	}

	return 0;	

}

 
 
 
 
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 integers a b c denotes an edge between a, b of cost c (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