参考题解

全 WA 得 0pts

record

给关注

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e5+10;
struct edge{
	int to,nxt,w;
}e[N<<1];
int head[N],idx,fr[N<<1],to[N<<1],w[N<<1];
void add(int x,int y,int z){
	e[++idx]={y,head[x],z};
	head[x]=idx;
	fr[idx]=x,to[idx]=y;w[idx]=z;
}
int siz[N],dep[N],son[N],fa[N];
int top[N],seg[N];
int val[N],a[N],dfn;
void dfs1(int u,int f,int depth){
	siz[u]=1;fa[u]=f;dep[u]=depth;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=f){
			dfs1(v,u,depth+1);
			val[v]=w[i];
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	seg[u]=++dfn;
	a[dfn]=val[u];
	if(!son[u])return;
	dfs2(son[u],u);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!seg[v])dfs2(v,v);
	}
}
struct segment{
	int l,r,mx,cov,add;
}tr[N<<2];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
inline void pushup(int p){tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);}
void build(int p,int l,int r){
	tr[p].l=l;tr[p].r=r;tr[p].cov=-1;
	if(l==r){tr[p].mx=a[l];return;}
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
void pushdown(int p){
	if(~tr[p].cov){
		tr[ls(p)].cov=tr[rs(p)].cov=tr[p].cov;
		tr[ls(p)].mx=tr[rs(p)].mx=tr[p].cov;
		tr[ls(p)].add=tr[rs(p)].add=0;
		tr[p].cov=-1;
	}
	if(tr[p].add){
		tr[ls(p)].add+=tr[p].add;
		tr[rs(p)].add+=tr[p].add;
		tr[ls(p)].mx+=tr[p].add;
		tr[rs(p)].mx+=tr[p].add;
		tr[p].add=0;
	}
}
void tree_cover(int p,int l,int r,int k){
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].mx=tr[p].cov=k;
		tr[p].add=0;
		return;
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)tree_cover(ls(p),l,r,k);
	if(mid<r)tree_cover(rs(p),l,r,k);
	pushup(p);
}
void tree_add(int p,int l,int r,int k){
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].add+=k;tr[p].mx+=k;
		return;
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)tree_add(ls(p),l,r,k);
	if(mid<r)tree_add(rs(p),l,r,k);
	pushup(p);
}
int tree_query(int p,int l,int r){
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].mx;
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	int ans=0;
	if(l<=mid)ans=max(ans,tree_query(ls(p),l,r));
	if(mid<r)ans=max(ans,tree_query(rs(p),l,r));
	return ans;
}
void seg_cover(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		tree_cover(1,seg[top[x]],seg[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	tree_cover(1,seg[x]+1,seg[y],k);
}
void seg_add(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		tree_add(1,seg[top[x]],seg[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	tree_add(1,seg[x]+1,seg[y],k);
}
int seg_query(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,tree_query(1,seg[top[x]],seg[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans=max(ans,tree_query(1,seg[x]+1,seg[y]));
	return ans;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	freopen("P4315_1.in","r",stdin);
	freopen("myout.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1,x,y,z;i<n;i++){
		cin>>x>>y>>z;
		add(x,y,z);add(y,x,z);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	string s;
	while(cin>>s&&s!="Stop"){
		int x,y,k;
		cin>>x>>y;
		if(s=="Change"){
			x<<=1;
			int u=fr[x],v=to[x];
			if(dep[u]>dep[v])swap(u,v);
			seg_cover(u,v,y);
		}
		if(s=="Cover"){
			cin>>k;
			seg_cover(x,y,k);
		}
		if(s=="Add"){
			cin>>k;
			seg_add(x,y,k);
		}
		if(s=="Max"){cout<<seg_query(x,y)<<endl;}
	}
	return 0;
}