[luogu4315]月下“毛景树”

luogu

联赛前复习一发树剖.不会告诉你WA了4发

#define ls x<<1,l,mid

#define rs x<<1|1,mid+1,r

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+5;

int re(){

	int x=0,w=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*w;

}

int n,cnt,ans,ts;

int mx[_<<2],tag[_<<2],cov[_<<2];

int h[_],dfn[_],val[_],son[_],id[_],sz[_],fa[_],dep[_],t[_],f[_];

struct edge{int to,next,w,id;}e[_<<1];

void link(int u,int v,int w,int id){

	e[++cnt]=(edge){v,h[u],w,id};h[u]=cnt;

	e[++cnt]=(edge){u,h[v],w,id};h[v]=cnt;

}

void dfs(int u){

	sz[u]=1;

	for(int i=h[u];i;i=e[i].next){

		int v=e[i].to;

		if(v==fa[u])continue;

		fa[v]=u;dep[v]=dep[u]+1;f[e[i].id]=v;

		dfs(v);sz[u]+=sz[v];val[v]=e[i].w;

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

	}

}

void dfs(int u,int tp){

	t[u]=tp;dfn[u]=++ts;id[ts]=u;

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

	for(int i=h[u];i;i=e[i].next){

		int v=e[i].to;

		if(v^son[u]&&v^fa[u])dfs(v,v);

	}

}

void pu(int x){mx[x]=max(mx[x<<1],mx[x<<1|1]);}

void pt(int x,int v){mx[x]+=v;tag[x]+=v;}

void cv(int x,int v){mx[x]=v;cov[x]=v;tag[x]=0;}

void pd(int x){

	if(cov[x])cv(x<<1,cov[x]),cv(x<<1|1,cov[x]),cov[x]=0;

	if(tag[x])pt(x<<1,tag[x]),pt(x<<1|1,tag[x]),tag[x]=0;

}

void bu(int x,int l,int r){

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

	int mid=l+r>>1;bu(ls);bu(rs);pu(x);

}

void mem(int x,int l,int r,int ql,int qr,int v){

	if(ql<=l&&r<=qr){cv(x,v);return;}pd(x);

	int mid=l+r>>1;if(ql<=mid)mem(ls,ql,qr,v);

	if(qr>mid)mem(rs,ql,qr,v);pu(x);

}

void add(int x,int l,int r,int ql,int qr,int v){

	if(ql<=l&&r<=qr){pt(x,v);return;}pd(x);

	int mid=l+r>>1;if(ql<=mid)add(ls,ql,qr,v);

	if(qr>mid)add(rs,ql,qr,v);pu(x);

}

int qmax(int x,int l,int r,int ql,int qr){

	if(ql<=l&&r<=qr)return mx[x];pd(x);int mid=l+r>>1;

	int res=-1e9;if(ql<=mid)res=qmax(ls,ql,qr);

	if(qr>mid)res=max(res,qmax(rs,ql,qr));return res;

}

void solve(int u,int v,int w,int o){

	while(t[u]^t[v]){

		if(dep[t[u]]<dep[t[v]])swap(u,v);

		if(o==1)add(1,1,n,dfn[t[u]],dfn[u],w);

		if(!o)mem(1,1,n,dfn[t[u]],dfn[u],w);

		if(o==2)ans=max(ans,qmax(1,1,n,dfn[t[u]],dfn[u]));

		u=fa[t[u]];

	}

	if(u==v)return;

	if(dep[u]<dep[v])swap(u,v);

	if(o==1)add(1,1,n,dfn[v]+1,dfn[u],w);

	if(!o)mem(1,1,n,dfn[v]+1,dfn[u],w);

	if(o==2)ans=max(ans,qmax(1,1,n,dfn[v]+1,dfn[u]));

}

int main(){

	n=re();

	for(int i=1,u,v,w;i<n;i++){

		u=re(),v=re(),w=re();

		link(u,v,w,i);

	}

	dfs(1);dfs(1,1);bu(1,1,n);

	char op[8];int u,v;

	while(1){

		scanf("%s",op);

		if(op[1]=='t')break;

		u=re(),v=re();

		if(op[1]=='o')solve(u,v,re(),0);

		if(op[1]=='d')solve(u,v,re(),1);

		if(op[1]=='a'){ans=-1e9;solve(u,v,0,2);printf("%d\n",ans);}

		if(op[1]=='h')mem(1,1,n,dfn[f[u]],dfn[f[u]],v);

	}

	return 0;

}