2017-12-12

Query on a tree I

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

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.

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

Input:

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

Output:

1
3

Solution

树链剖分裸体
md 我一开始看成了加和打了树上差分过了样例
被cxy一语点醒
顿时世界都黑了 mmpmmp

#include <bits/stdc++.h>
using namespace std;
#define maxn (int)(1e5+10)
#define LL long long
pair<int,int>mp[maxn];
inline int read(){
	int rtn=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))rtn=(rtn<<1)+(rtn<<3)+ch-'0',ch=getchar();
	return rtn*f;
}
int cnt,n,coc,m,p[maxn],size[maxn],son[maxn],dfn[maxn],top[maxn],dep[maxn],id[maxn],fa[maxn],w[maxn];
struct node{
	int a,b,nt,w;
}e[maxn<<1];
inline void add(int x,int y,int z){
	e[++cnt].a=x;e[cnt].b=y;e[cnt].w=z;
	e[cnt].nt=p[x];p[x]=cnt;
}
inline void dfs1(int k){
	size[k]=1;
	for(int i=p[k];i;i=e[i].nt){
		int kk=e[i].b;
		if(kk==fa[k])continue;
		fa[kk]=k;
		dep[kk]=dep[k]+1;
		w[kk]=e[i].w;
		dfs1(kk);
		size[k]+=size[kk];
		if(size[kk]>size[son[k]])son[k]=kk;
	}
}
inline void dfs2(int x,int y){
	top[x]=y;dfn[x]=++coc;id[coc]=x;
	if(!son[x])return;
	dfs2(son[x],y);
	for(int i=p[x];i;i=e[i].nt){
		int k=e[i].b;
		if(k==fa[x]||k==son[x])continue;
		dfs2(k,k);
	}
}
namespace Link_Chain_SegmentTree{
	LL maxv[maxn<<3];
	inline void build(int p,int l,int r){
		if(l==r)return (void)(maxv[p]=w[id[l]]);
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		maxv[p]=max(maxv[p<<1],maxv[p<<1|1]);
	}
	inline LL query(int p,int lp,int rp,int l,int r){
		if(l>r)return 0;
		if(l==lp&&r==rp)return maxv[p];
		int mid=lp+rp>>1;
		if(r<=mid)return query(p<<1,lp,mid,l,r);
		else if(l>mid)return query(p<<1|1,mid+1,rp,l,r);
		else return max(query(p<<1,lp,mid,l,mid),query(p<<1|1,mid+1,rp,mid+1,r));
	}
	inline LL query_chain(int x,int y){
		LL rtn=0;
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			rtn=max(rtn,query(1,1,n,dfn[top[x]],dfn[x]));
			x=fa[top[x]]; 
		}if(dep[x]>dep[y])swap(x,y);
		return max(rtn,query(1,1,n,dfn[x]+1,dfn[y]));
	}
	inline void update(int p,int lp,int rp,int pos,LL val){
		if(lp>rp)return;
		if(lp==rp)return (void)(maxv[p]=val);
		int mid=lp+rp>>1;
		if(pos<=mid)update(p<<1,lp,mid,pos,val);
		else update(p<<1|1,mid+1,rp,pos,val);
		maxv[p]=max(maxv[p<<1],maxv[p<<1|1]);
	}
	inline void update_chain(int id, LL val){
		int from=mp[id].first,to=mp[id].second;
		if(dep[from]>dep[to])update(1,1,n,dfn[from],val);
		else update(1,1,n,dfn[to],val);
	}
}using namespace Link_Chain_SegmentTree;
int main(){
	int T;scanf("%d",&T);
	while(T--){
		n;scanf("%d",&n);coc=0;
		memset(p,0,sizeof(p));
		memset(fa,0,sizeof(fa));
		memset(son,0,sizeof(son));
		for(int i=1;i<n;i++){
			mp[i].first=read();mp[i].second=read();int w=read();
			add(mp[i].first,mp[i].second,w); 
			add(mp[i].second,mp[i].first,w); 
		}
		dfs1(1);dfs2(1,1) ;
		build(1,1,n);
		while(true){
			char ch[10];scanf("%s",ch);
			if(ch[0]=='D')break;
			int x=read(),y=read();
			if(ch[0]=='Q')printf("%lld\n",query_chain(x,y));
			if(ch[0]=='C')update_chain(x,y);
		}
	}
	return 0;
}
/*
1
10
2 1 6824
3 1 21321
4 2 26758
5 1 13610
6 4 19133
7 4 20483
8 7 10438
9 8 19157
10 6 25677
C 2 11799
Q 5 6
Q 6 10
Q 3 1
C 5 9242
C 3 15761
C 2 28270
C 8 8177
C 5 21007
Q 4 8
D
*/