RT 只有最后一个点A了(还是hack数据。。)
看了前面的帖子,我pushdown都加了啊……
求助大佬帮忙挑错(加深印象啊)
代码如下:
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
#define MAXN 400005
#define INF 1<<30
#define re register
int n,head[MAXN],tot,rk[MAXN];
struct node{
int to,next,w,d;
node(int a=0,int b=0,int c=0)
:to(a),next(b),w(c){}
}bian[MAXN];
struct node1{
int fa,zson,top,size,id,d,v;
}e[MAXN];
struct node2{
int l,r,sum,maxn,minn,flz;
}t[MAXN<<2];
inline int read(){
int w=0,f=1;
char c=getchar();
while (c>'9'||c<'0'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0'&&c<='9'){
w=(w<<3)+(w<<1)+(c^48);
c=getchar();
}
return w*f;
}
inline void adde(int u,int v,int w){
bian[++tot]=node(v,head[u],w);
head[u]=tot;
}
void dfs1(int x){
e[x].d=e[e[x].fa].d+1,e[x].size=1;
for (re int i=head[x];i;i=bian[i].next){
int to=bian[i].to;
if (to!=e[x].fa){
e[to].v=bian[i].w;
bian[i].d=to;
e[to].fa=x;
dfs1(to);
e[x].size+=e[to].size;
if (e[to].size>e[e[x].zson].size)
e[x].zson=to;
}
}
}
void dfs2(int u,int tp){
e[u].top=tp,e[u].id=++tot,rk[tot]=u;
if (e[u].zson) dfs2(e[u].zson,tp);
for (re int i=head[u];i;i=bian[i].next){
int v=bian[i].to;
if (v!=e[u].fa&&v!=e[u].zson)
dfs2(v,v);
}
}
inline void update(int i){
t[i].sum=t[i<<1].sum+t[i<<1|1].sum;
t[i].maxn=max(t[i<<1].maxn,t[i<<1|1].maxn);
t[i].minn=min(t[i<<1].minn,t[i<<1|1].minn);
}
void build(int i,int l,int r){
t[i].l=l,t[i].r=r;
if (l==r){
t[i].maxn=t[i].minn=t[i].sum=e[rk[l]].v;
return;
}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
update(i);
}
inline int len(int i){
return t[i].r-t[i].l+1;
}
inline void pushdown(int i){
if (t[i].flz){
t[i<<1].sum*=-1;
t[i<<1|1].sum*=-1;
t[i<<1].flz^=1;
t[i<<1|1].flz^=1;
int zc=-t[i<<1].minn;
t[i<<1].minn=-t[i<<1].maxn;
t[i<<1].maxn=zc;
zc=-t[i<<1|1].minn;
t[i<<1|1].minn=-t[i<<1|1].maxn;
t[i<<1|1].maxn=zc;
t[i].flz=0;
}
}
void assign(int i,int dis,int k){
if (t[i].l==t[i].r){
t[i].sum=t[i].maxn=t[i].minn=k;
return;
}
pushdown(i);
if (t[i<<1].r>=dis) assign(i<<1,dis,k);
else assign(i<<1|1,dis,k);
update(i);
}
inline void assign_(int i,int w){
if (bian[i<<1].d) assign(1,bian[i<<1].d,w);
else assign(1,bian[(i<<1)-1].d,w);
}
void dao(int i,int l,int r){
if (t[i].l>=l&&t[i].r<=r){
t[i].sum*=-1;
t[i].flz^=1;
int zc=-t[i].minn;
t[i].minn=-t[i].maxn;
t[i].maxn=zc;
return;
}
pushdown(i);
if (t[i<<1].r>=l) dao(i<<1,l,r);
if (t[i<<1|1].l<=r) dao(i<<1|1,l,r);
update(i);
}
inline void dao_(int x,int y){
while (e[x].top!=e[y].top){
if (e[x].top<e[y].top) swap(x,y);
dao(1,e[e[x].top].id,e[x].id);
x=e[e[x].top].fa;
}
if (e[x].id>e[y].id) swap(x,y);
dao(1,e[x].id+1,e[y].id);
}
int sum(int i,int l,int r){
if (t[i].l>=l&&t[i].r<=r) return t[i].sum;
pushdown(i);
int s=0;
if (t[i<<1].r>=l) s+=sum(i<<1,l,r);
if (t[i<<1|1].l<=r) s+=sum(i<<1|1,l,r);
return s;
}
inline int sum_(int x,int y){
int ans=0;
while (e[x].top!=e[y].top){
if (e[x].top<e[y].top) swap(x,y);
ans+=sum(1,e[e[x].top].id,e[x].id);
x=e[e[x].top].fa;
}
if (e[x].id>e[y].id) swap(x,y);
return ans+sum(1,e[x].id+1,e[y].id);
}
int maxn(int i,int l,int r){
if (t[i].l>=l&&t[i].r<=r) return t[i].maxn;
pushdown(i);
int s=-INF;
if (t[i<<1].r>=l) s=max(s,maxn(i<<1,l,r));
if (t[i<<1|1].l<=r) s=max(s,maxn(i<<1|1,l,r));
return s;
}
inline int maxn_(int x,int y){
int ans=-INF;
while (e[x].top!=e[y].top){
if (e[x].top<e[y].top) swap(x,y);
ans=max(ans,maxn(1,e[e[x].top].id,e[x].id));
x=e[e[x].top].fa;
}
if (e[x].id>e[y].id) swap(x,y);
return max(ans,maxn(1,e[x].id+1,e[y].id));
}
int minn(int i,int l,int r){
if (t[i].l>=l&&t[i].r<=r) return t[i].minn;
pushdown(i);
int s=INF;
if (t[i<<1].r>=l) s=min(s,minn(i<<1,l,r));
if (t[i<<1|1].l<=r) s=min(s,minn(i<<1|1,l,r));
return s;
}
inline int minn_(int x,int y){
int ans=INF;
while (e[x].top!=e[y].top){
if (e[x].top<e[y].top) swap(x,y);
ans=min(ans,minn(1,e[e[x].top].id,e[x].id));
x=e[e[x].top].fa;
}
if (e[x].id>e[y].id) swap(x,y);
return min(ans,minn(1,e[x].id+1,e[y].id));
}
int main(){
n=read();
for (re int i=1;i<n;i++){
int u=read()+1,v=read()+1,w=read();
adde(u,v,w),adde(v,u,w);
}
dfs1(1);tot=0;dfs2(1,1);
build(1,1,n);
re int q=read();
while (q--){
string s;
cin>>s;
int a=read(),b=read();
if (s=="C") assign_(a,b);
else if (s=="N") dao_(a+1,b+1);
else if (s=="SUM") printf("%d\n",sum_(a+1,b+1));
else if (s=="MAX") printf("%d\n",maxn_(a+1,b+1));
else printf("%d\n",minn_(a+1,b+1));
}
return 0;
}
就207行不多吧