列表

详情


NC210168. 月下“毛景树”

描述

毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝,但节点上是没有毛毛果的,毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力,他能改变树枝上毛毛果的个数:  Change k w:将第k条树枝上毛毛果的个数改变为w个。  Cover u v w:将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。  Add u v w:将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪,于是他会有如下询问:  Max u v:询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

输入描述

第一行一个正整数N。 接下来N-1行,每行三个正整数Ui,Vi和Wi,第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi,树枝上有Wi个毛毛果。 接下来是操作和询问,以“Stop”结束。

输出描述

对于毛毛虫的每个询问操作,输出一个答案。

示例1

输入:

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

输出:

9
16

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 410ms, 内存消耗: 20504K, 提交时间: 2023-03-20 21:22:44

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;

struct E{
	int v,w,nxt;
}e[N];
int head[N],cnt=1;

inline void addedge(int u,int v,int w){
	e[++cnt]=(E){v,w,head[u]};head[u]=cnt;
}

int sz[N],dep[N],son[N],fa[N],val[N],eid[N];
int idx=0,dfn[N],idfn[N],bel[N];

void dfs1(int x,int f){
	dep[x]=dep[f]+1;
	fa[x]=f;sz[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].v;
		if(to==f) continue;
		val[to]=e[i].w;
		eid[i/2]=to;
		dfs1(to,x);
		sz[x]+=sz[to];
		if(sz[to]>sz[son[x]]) son[x]=to;
	}
}

void dfs2(int x,int tp){
	bel[x]=tp;
	dfn[x]=++idx;idfn[idx]=x;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].v;
		if(to==fa[x]||to==son[x]) continue;
		dfs2(to,to);
	}
}


int mx[N<<2],add[N<<2],cov[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)

void pushdown(int p,int l,int r){
	if(cov[p]!=-1){
		mx[ls]=mx[rs]=cov[p];
		cov[ls]=cov[rs]=cov[p];
		add[ls]=add[rs]=0;
		cov[p]=-1;
	}
	if(add[p]){
		mx[ls]+=add[p];mx[rs]+=add[p];
		add[ls]+=add[p];add[rs]+=add[p];
		add[p]=0;
	}
}

void build(int p,int l,int r){
	cov[p]=-1;add[p]=0;
	if(l==r){
		mx[p]=val[idfn[l]];
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	mx[p]=max(mx[ls],mx[rs]);
}

void modify(int p,int l,int r,int ql,int qr,int w){
	if(ql>qr) return;
	if(ql<=l&&r<=qr){
		mx[p]=cov[p]=w;
		add[p]=0;
		return;
	}
	pushdown(p,l,r);
	if(ql<=mid) modify(ls,l,mid,ql,qr,w);
	if(qr>mid) modify(rs,mid+1,r,ql,qr,w);
	mx[p]=max(mx[ls],mx[rs]);
}

void update(int p,int l,int r,int ql,int qr,int w){
	if(ql>qr) return;
	if(ql<=l&&r<=qr){
		mx[p]+=w;add[p]+=w;
		return;
	}
	pushdown(p,l,r);
	if(ql<=mid) update(ls,l,mid,ql,qr,w);
	if(qr>mid) update(rs,mid+1,r,ql,qr,w);
	mx[p]=max(mx[ls],mx[rs]);
}

int query(int p,int l,int r,int ql,int qr){
	if(ql>qr) return 0;
	if(ql<=l&&r<=qr) return mx[p];
	pushdown(p,l,r);
	int res=0;
	if(ql<=mid) res=query(ls,l,mid,ql,qr);
	if(qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;string str;
	cin>>n;
	for(int i=1,u,v,w;i<n;++i){
		cin>>u>>v>>w;
		addedge(u,v,w);
		addedge(v,u,w);
	}
	val[1]=0;dep[1]=1;
	dfs1(1,0);
	dfs2(1,1); //树链剖分
	build(1,1,n);
//	for(int i=1;i<=n;++i) cout<<i<<" "<<val[i]<<" "<<dfn[i]<<" "<<idfn[i]<<" "<<" ~~\n";
	int k,u,v,w;
	cin>>str;
	while(str!="Stop"){
		if(str=="Change"){
			cin>>k>>w;
			int to=eid[k];
			modify(1,1,n,dfn[to],dfn[to],w);
		}else if(str=="Cover"){
			cin>>u>>v>>w;
			while(bel[u]^bel[v]){
				if(dep[bel[u]]<dep[bel[v]]) swap(u,v);
				modify(1,1,n,dfn[bel[u]],dfn[u],w);
				u=fa[bel[u]];
			}
			if(dep[u]<dep[v]) swap(u,v);
			modify(1,1,n,dfn[v]+1,dfn[u],w);
		}else if(str=="Add"){
			cin>>u>>v>>w;
			while(bel[u]^bel[v]){
				if(dep[bel[u]]<dep[bel[v]]) swap(u,v);
				update(1,1,n,dfn[bel[u]],dfn[u],w);
				u=fa[bel[u]];
			}
			if(dep[u]<dep[v]) swap(u,v);
			update(1,1,n,dfn[v]+1,dfn[u],w);
		}else if(str=="Max"){
			cin>>u>>v;
			int ans=0;
			while(bel[u]^bel[v]){
				if(dep[bel[u]]<dep[bel[v]]) swap(u,v);
//				cout<<" "<<bel[u]<<" "<<u<<" "<<idfn[bel[u]]<<" "<<idfn[u]<<" "<<query(1,1,n,dfn[bel[u]],dfn[u])<<"!!\n"; 
				ans=max(ans,query(1,1,n,dfn[bel[u]],dfn[u]));
				u=fa[bel[u]];
			}
			if(dep[u]<dep[v]) swap(u,v);
			ans=max(ans,query(1,1,n,dfn[v]+1,dfn[u]));
			cout<<ans<<"\n";
		}
		cin>>str; 
	} 
	return 0;
}

上一题