学步园

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1984

太久没写边权链剖手都生了,居然调了一个多小时,看来有空必须练练代码能力

Code:

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cctype>
using namespace std;
const int maxn=1e5+5;
struct edge{int u,v,w;};
vector<edge>G[maxn];
vector<edge>edges;
int fa[maxn],dep[maxn],top[maxn],siz[maxn],son[maxn],w[maxn],mp[maxn],rmp[maxn],z;
int n,m;
int getint(){
	int res=0,f=1;char c=getchar();
	while(!isdigit(c))f=f==-1||c=='-'?-1:1,c=getchar();
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res*f;
}
void dfs(int u){
	siz[u]=1;
	for(int i=0;i<G[u].size();i++){
		edge e=G[u][i];
		if(e.v!=fa[u]){
			w[e.v]=e.w;fa[e.v]=u;dep[e.v]=dep[u]+1;
			dfs(e.v);
			siz[u]+=siz[e.v];
			if(siz[son[u]]<siz[e.v])son[u]=e.v;
		}
	}
}
void build(int u,int tp){
	mp[u]=++z;rmp[z]=u;top[u]=tp;
	if(son[u])build(son[u],tp);
	for(int i=0;i<G[u].size();i++){
		edge e=G[u][i];
		if(e.v!=fa[u]&&e.v!=son[u])build(e.v,e.v);
	}
}
struct seg{
	struct node{
		int lazy,mx,cov;
		node():
			lazy(0),mx(0),cov(-1){};
	}t[maxn<<2];
	#define lson i<<1,l,mid
	#define rson i<<1|1,mid+1,r
	#define L i<<1
	#define R i<<1|1
	void pushdown(int i,int l,int r){
		int mid=(l+r)>>1;
		if(~t[i].cov){
			t[L].mx=t[L].cov=t[i].cov;
			t[R].mx=t[R].cov=t[i].cov;
			t[L].lazy=t[R].lazy=0;
			t[i].cov=-1;
		}
		if(t[i].lazy){
			t[L].mx+=t[i].lazy;
			t[R].mx+=t[i].lazy;
			if(~t[L].cov)t[L].cov+=t[i].lazy;
			else t[L].lazy+=t[i].lazy;
			if(~t[R].cov)t[R].cov+=t[i].lazy;
			else t[R].lazy+=t[i].lazy;
			t[i].lazy=0;	
		}
	}
	void rz(int i){
		t[i].mx=max(t[L].mx,t[R].mx);
	}
	void Add(int i,int l,int r,int l0,int r0,int d){
		if(l0>r0)swap(l0,r0);
		if(l0<=l&&r0>=r){
			t[i].lazy+=d;
			t[i].mx+=d;
			return;
		}pushdown(i,l,r);
		int mid=(l+r)>>1;
		if(l0<=mid)Add(lson,l0,r0,d);
		if(r0>mid)Add(rson,l0,r0,d);
		rz(i);
	}
	void Cover(int i,int l,int r,int l0,int r0,int d){
		if(l0>r0)swap(l0,r0);
		if(l0<=l&&r0>=r){
			t[i].cov=d;
			t[i].mx=d;
			t[i].lazy=0;
			return;
		}pushdown(i,l,r);
		int mid=(l+r)>>1;
		if(l0<=mid)Cover(lson,l0,r0,d);
		if(r0>mid)Cover(rson,l0,r0,d);
		rz(i);		
	}
	int Max(int i,int l,int r,int l0,int r0){
		if(l0>r0)swap(l0,r0);
		if(l0<=l&&r0>=r)return t[i].mx;
		pushdown(i,l,r);
		int mid=(l+r)>>1,ans=0;
		if(l0<=mid)ans=max(ans,Max(lson,l0,r0));
		if(r0>mid)ans=max(ans,Max(rson,l0,r0));
		return ans;
	}
}T;
void Add(int u,int v,int x){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		T.Add(1,1,n,mp[u],mp[top[u]],x);
		u=fa[top[u]];
	}if(u!=v)T.Add(1,1,n,min(mp[u],mp[v])+1,max(mp[u],mp[v]),x);
}
void Cover(int u,int v,int x){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		T.Cover(1,1,n,mp[u],mp[top[u]],x);
		u=fa[top[u]];
	}if(u!=v)T.Cover(1,1,n,min(mp[u],mp[v])+1,max(mp[u],mp[v]),x);
}
int Max(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		ans=max(ans,T.Max(1,1,n,mp[u],mp[top[u]]));
		u=fa[top[u]];
	}if(u!=v)ans=max(ans,T.Max(1,1,n,min(mp[u],mp[v])+1,max(mp[u],mp[v])));
	return ans;
}
int main(){
	n=getint();
	for(int i=1;i<n;i++){
		int u=getint(),v=getint(),w=getint();
		edges.push_back((edge){u,v,w});
		G[u].push_back((edge){u,v,w});
		G[v].push_back((edge){v,u,w});
	}dfs(1);
	build(1,1);
	for(int i=1;i<=n;i++)
	T.Cover(1,1,n,i,i,w[rmp[i]]);
	while(1){
		char op[10];
		scanf("%s",op);
		if(op[0]=='A'){
			int u=getint(),v=getint(),x;
			Add(u,v,getint());
		}else
		if(op[0]=='M'){
			int u=getint(),v=getint(),x;
			printf("%d\n",Max(u,v));
		}else
		if(op[1]=='h'){
			int k=getint(),w=getint();
			int u=fa[edges[k-1].u]==edges[k-1].v?edges[k-1].u:edges[k-1].v;
			Cover(fa[u],u,w);
		}else
		if(op[1]=='o'){
			int u=getint(),v=getint(),x;
			Cover(u,v,getint());
		}else break;
	}
	return 0;
}