树剖求调!!
查看原帖
树剖求调!!
564732
TimSwn090306楼主2023/3/11 15:49

全WA,相反操作 用的是全*-1,不知道哪里有错qwq

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+1;
const int maxm=2e5+1;
const int inf=0x3f3f3f3f;
struct edge{
	int to,w,next;
}e[maxm<<1];
struct segment{
	int l,r;
	int val,mul,add;
	int minn,maxx;
}c[maxn<<2];
int n,m,tot,h[maxn],w[maxn],cw[maxn];
int tim,fa[maxn],dep[maxn],siz[maxn],son[maxn],id[maxn],top[maxn];
inline void addEdge(int x,int y,int z){
	e[++tot]=(edge){y,z,h[x]};
	h[x]=tot;
}
inline void build(int root,int l,int r){
	c[root].l=l;
	c[root].r=r;
	c[root].mul=1;
	c[root].add=0;
	if (l==r) c[root].val=c[root].minn=c[root].maxx=cw[l];
	else{
		int mid=l+r>>1;
		build(root<<1,l,mid);
		build(root<<1|1,mid+1,r);
		c[root].val=c[root<<1].val+c[root<<1|1].val;
		c[root].minn=min(c[root<<1].minn,c[root<<1|1].minn);
		c[root].maxx=max(c[root<<1].maxx,c[root<<1|1].maxx);
	}
}
inline void pushdown(int root){
	c[root<<1].val=(c[root<<1].val*c[root].mul+(c[root<<1].r-c[root<<1].l+1)*c[root].add);
	c[root<<1].add=(c[root<<1].add*c[root].mul+c[root].add);
	c[root<<1].mul=(c[root<<1].mul*c[root].mul);
	c[root<<1|1].val=(c[root<<1|1].val*c[root].mul+(c[root<<1|1].r-c[root<<1|1].l+1)*c[root].add);
	c[root<<1|1].add=(c[root<<1|1].add*c[root].mul+c[root].add);
	c[root<<1|1].mul=(c[root<<1|1].mul*c[root].mul);
	c[root].add=0;
	c[root].mul=1;
}
inline void cupd1(int root,int l,int r,int dat){
	if (l>c[root].r || r<c[root].l) return ;
	if (l<=c[root].l && r>=c[root].r){
		c[root].val+=dat*(c[root].r-c[root].l+1);
		c[root].add+=dat;
		c[root].minn+=dat;
		c[root].maxx+=dat;
		return ;
	}
	pushdown(root);
	cupd1(root<<1,l,r,dat);
	cupd1(root<<1|1,l,r,dat);
	c[root].val=c[root<<1].val+c[root<<1|1].val;
	c[root].minn=min(c[root<<1].minn,c[root<<1|1].minn);
	c[root].maxx=max(c[root<<1].maxx,c[root<<1|1].maxx);
}
inline void cupd2(int root,int l,int r,int dat){
	if (l>c[root].r || r<c[root].l) return ;
	if (l<=c[root].l && r>=c[root].r){
		c[root].val*=dat;
		int mn=c[root].minn,mx=c[root].maxx;
		c[root].minn=min(mn*dat,mx*dat);
		c[root].maxx=max(mn*dat,mx*dat);
		c[root].add*=dat;
		c[root].mul*=dat;
		return ;
	}
	pushdown(root);
	cupd2(root<<1,l,r,dat);
	cupd2(root<<1|1,l,r,dat);
	c[root].val=c[root<<1].val+c[root<<1|1].val;
	c[root].minn=min(c[root<<1].minn,c[root<<1|1].minn);
	c[root].maxx=max(c[root<<1].maxx,c[root<<1|1].maxx);
}
inline int cgetsum(int root,int l,int r){
	if (l>c[root].r || r<c[root].l) return 0;
	if (l<=c[root].l && r>=c[root].r) return c[root].val;
	pushdown(root);
	return cgetsum(root<<1,l,r)+cgetsum(root<<1|1,l,r);
}
inline int cgetmin(int root,int l,int r){
	if (l>c[root].r || r<c[root].l) return inf;
	if (l<=c[root].l && r>=c[root].r) return c[root].val;
	pushdown(root);
	return min(cgetmin(root<<1,l,r),cgetmin(root<<1|1,l,r));
}
inline int cgetmax(int root,int l,int r){
	if (l>c[root].r || r<c[root].l) return -inf;
	if (l<=c[root].l && r>=c[root].r) return c[root].val;
	pushdown(root);
	return max(cgetmax(root<<1,l,r),cgetmax(root<<1|1,l,r));
}
inline void dfs1(int x,int f,int d){
	fa[x]=f;
	dep[x]=d;
	siz[x]=1;
	int maxx=-1;
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==f) continue;
		dfs1(v,x,d+1);
		siz[x]+=siz[v];
		w[v]=e[i].w;
		if (siz[v]>maxx){
			son[x]=v;
			maxx=siz[v];
		}
	}
}
inline void dfs2(int x,int topf){
	id[x]=++tim;
	cw[id[x]]=w[x];
	top[x]=topf;
	if (son[x]) dfs2(son[x],topf);
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==son[x] || v==fa[x]) continue;
		dfs2(v,v);
	}
}
inline void upd1(int x,int y,int dat){
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		cupd1(1,id[top[x]],id[x],dat);
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	if (x!=y) cupd1(1,id[y]+1,id[x],dat);
}
inline void upd2(int x,int y,int dat){
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		cupd2(1,id[top[x]],id[x],dat);
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	if (x!=y) cupd2(1,id[y]+1,id[x],dat);
}
inline int getsum(int x,int y){
	int res=0;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		res+=cgetsum(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	if (x!=y) res+=cgetsum(1,id[y]+1,id[x]);
	return res;
}
inline int getmin(int x,int y){
	int res=inf;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		res=min(res,cgetmin(1,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	if (x!=y) res=min(res,cgetmin(1,id[y]+1,id[x]));
	return res;
}
inline int getmax(int x,int y){
	int res=-inf;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		res=max(res,cgetmax(1,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	if (x!=y) res=max(res,cgetmax(1,id[y]+1,id[x]));
	return res;
}
int main(){
	scanf("%d",&n);
	for (int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		addEdge(u,v,w);
		addEdge(v,u,w);
	}
	dfs1(0,n+1,1);
	dfs2(0,0);
	build(1,1,n);	
	scanf("%d",&m);
	for (int i=1,u,v;i<=m;i++){
		string op;
		cin>>op;
		scanf("%d%d",&u,&v);
		if (op=="C"){
			int target=e[(u-1)<<1|1].to;
			cupd2(1,id[target],id[target],0);
			cupd1(1,id[target],id[target],v);
		}else if (op=="N") upd2(u,v,-1);
		else if (op=="SUM") printf("%d\n",getsum(u,v));
		else if (op=="MAX") printf("%d\n",getmax(u,v));
		else if (op=="MIN") printf("%d\n",getmin(u,v));
	}
	return 0;
}

救救调了两天半的蒟蒻罢ovo

2023/3/11 15:49
加载中...