码风良好树剖板题求调
查看原帖
码风良好树剖板题求调
808222
Kotobuki_Tsumugi楼主2024/4/20 13:25

样例过了但是全WA。自己对拍了一组,发现问题大概是点权转边权时修改操作的错误,但是不知道怎么调。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int n,m,root,MOD;
int w[N],siz[N],dfn[N],son[N];
int top[N],fa[N],dep[N],cnt;
int idx,h[N],ne[N],e[N],a[N],u[N],v[N];
struct{
	int max,Lazt,res = 0;
}tree[N<<2];
void add(int x,int y){
	e[idx] = y;
	ne[idx] = h[x];
	h[x] = idx++;
}
inline int ls(int x){return x<<1;}
inline int rs(int x){return (x<<1)|1;}
inline void Push_up(int p){
	tree[p].max = max(tree[ls(p)].max,tree[rs(p)].max);
}
void res_down(int s,int t,int p){
	if(tree[p].res != 0){
		tree[ls(p)].max = tree[p].res;
		tree[rs(p)].max = tree[p].res;
		tree[ls(p)].res = tree[p].res;
		tree[rs(p)].res = tree[p].res;
		tree[ls(p)].Lazt = 0;
		tree[rs(p)].Lazt = 0;
		tree[p].res = 0;
	}
}
void Lazt_down(int s,int t,int p){
	if(tree[p].Lazt){
		tree[ls(p)].max += tree[p].Lazt;
		tree[rs(p)].max += tree[p].Lazt;
		tree[ls(p)].Lazt += tree[p].Lazt;
		tree[rs(p)].Lazt += tree[p].Lazt;
		tree[p].Lazt = 0;
	}
}
void Push_down(int s,int t,int p){
	res_down(s,t,p);
	Lazt_down(s,t,p);
}
void Build(int s,int t,int p){
	if(s == t){
		tree[p].max = a[s];
		tree[p].Lazt = 0;
		tree[p].res = 0;
		return;
	}
	int mid = s+((t-s)>>1);
	Build(s,mid,ls(p));
	Build(mid+1,t,rs(p));
	Push_up(p);
}
void Update1(int l,int r,int k,int s,int t,int p){
	if(l <= s && t <= r){
		tree[p].max = k;
		tree[p].res = k;
		tree[p].Lazt = 0;
		return;
	}
	Push_down(s,t,p);
	int mid = s+((t-s)>>1);
	if(l <= mid) Update1(l,r,k,s,mid,ls(p));
	if(r > mid)  Update1(l,r,k,mid+1,t,rs(p));
	Push_up(p); 
}
void Update2(int l,int r,int k,int s,int t,int p){
	if(l <= s && t <= r){
		res_down(s,t,p);
		tree[p].max += k;
		tree[p].Lazt += k;
		return;
	}
	Push_down(s,t,p);
	int mid = s+((t-s)>>1);
	if(l <= mid) Update2(l,r,k,s,mid,ls(p));
	if(r > mid)  Update2(l,r,k,mid+1,t,rs(p));
	Push_up(p); 
}
int Getsum(int l,int r,int s,int t,int p){
	if(l <= s && t <= r) return tree[p].max;
	Push_down(s,t,p);
	int mid = s+((t-s)>>1),ans = 0;
	if(l <= mid) ans = max(ans,Getsum(l,r,s,mid,ls(p)));
	if(r > mid)  ans = max(ans,Getsum(l,r,mid+1,t,rs(p)));
	return ans;
}
void dfs1(int u,int father){
	fa[u] = father; siz[u] = 1;
	dep[u] = dep[father]+1;
	for(int i = h[u];i != -1;i = ne[i]){
		if(e[i] == father) continue;
		int v = e[i]; dfs1(v,u);
		siz[u] += siz[v];
		if(son[u] == 0 || siz[v] > siz[son[u]])
			son[u] = v;
	}
}
void dfs2(int u,int topx){
	top[u] = topx;
	dfn[u] = ++cnt;
	a[dfn[u]] = w[u];
	if(son[u] == 0) return;
	dfs2(son[u],topx);
	for(int i = h[u];i != -1;i = ne[i]){
		if(e[i] == fa[u]) continue;
		if(e[i] == son[u]) continue;
		int v = e[i]; dfs2(v,v);
	}
}
void Update_range1(int x,int y,int k){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) 
			swap(x,y);
		Update1(dfn[top[x]],dfn[x],k,1,n,1);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x,y);
	if(x != y) Update1(dfn[x]+1,dfn[y],k,1,n,1);
}
void Update_range2(int x,int y,int k){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) 
			swap(x,y);
		Update2(dfn[top[x]],dfn[x],k,1,n,1);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x,y);
	if(x != y) Update2(dfn[x]+1,dfn[y],k,1,n,1);
}
void Update_range3(int k,int w){
	Update1(u[k],v[k],w,1,n,1);
}
void Query_range(int x,int y){
	int ans = 0;
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) 
			swap(x,y);
		ans = max(Getsum(dfn[top[x]],dfn[x],1,n,1),ans); 
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x,y);
	if(x != y) ans = max(Getsum(dfn[x]+1,dfn[y],1,n,1),ans);
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n; root = 1;
	memset(h,-1,sizeof(h));
	for(int i = 1;i<n;i++){
		cin>>u[i]>>v[i];
		cin>>w[u[i]];
		add(u[i],v[i]); 
		add(v[i],u[i]);
	}
	dfs1(root,0);
	dfs2(root,root);
	Build(1,n,1);
	while(true){
		string s;
		int x,y,k;
		cin>>s;
		if(s == "Stop") break;
		else if(s == "Max")    cin>>x>>y,   Query_range(x,y);
		else if(s == "Add")    cin>>x>>y>>k,Update_range2(x,y,k);
		else if(s == "Cover")  cin>>x>>y>>k,Update_range1(x,y,k);
		else if(s == "Change") cin>>x>>k,   Update_range3(x,k);
		//Query_range(2,4);
	}
	return 0;
}
2024/4/20 13:25
加载中...