调代码过程中,蒟蒻在每次循环后输出了每个点的值,发现如果每次操作后查询一下每个点的值(注释里的代码)的话答案就是正确的,但不查询答案就不对,可以把注释去掉再跑一遍会发现结果不一样,能问问这是为啥吗?
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
ll a=0,x=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') x=-x;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
a=(a<<1)+(a<<3)+(ch^48);
ch=getchar();
}
return a*x;
}
const int N=4e5;
int n,tim,Edge;
int head[N],val[N],dfn[N],dep[N],size[N],Id[N],Fa[N],top[N],son[N];
int sum[N<<2],lazy1[N<<2],lazy2[N<<2];
char opt[10];
struct node
{
int from,to,nxt,dis;
}a[N<<1];
void add(int from,int to,int dis)
{
Edge++;
a[Edge].from=from;
a[Edge].to=to;
a[Edge].dis=dis;
a[Edge].nxt=head[from];
head[from]=Edge;
}
void dfs1(int u,int fa)
{
dep[u]=dep[fa]+1;
size[u]=1;
for(int i=head[u];i;i=a[i].nxt)
{
int v=a[i].to;
if(v==fa) continue;
val[v]=a[i].dis;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
Fa[v]=u;
}
}
void dfs2(int u,int fa)
{
if(u==0) return ;
dfn[u]=++tim;
Id[tim]=u;
if(u==son[fa]) top[u]=top[fa];
else top[u]=u;
dfs2(son[u],u);
for(int i=head[u];i;i=a[i].nxt)
{
int v=a[i].to;
if(v==fa||v==son[u]) continue;
dfs2(v,u);
}
}
void update(int node)
{
sum[node]=max(sum[node<<1],sum[node<<1|1]);
}
void build(int node,int l,int r)
{
lazy1[node]=lazy2[node]=-1;
if(l==r)
{
sum[node]=val[Id[l]];
return ;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
update(node);
//printf("%d %d %d???\n",l,r,sum[node]);
}
void pushdown(int node,int l,int r)
{
int mid=(l+r)>>1;
if(lazy1[node]!=-1)
{
lazy1[node<<1]=lazy1[node];
lazy1[node<<1|1]=lazy1[node];
sum[node<<1]=lazy1[node];
sum[node<<1|1]=lazy1[node];
lazy1[node]=lazy2[node]=-1;
}
if(lazy2[node]!=-1)
{
lazy2[node<<1]+=lazy2[node]+(lazy2[node<<1]==-1);
lazy2[node<<1|1]+=lazy2[node]+(lazy2[node<<1|1]==-1);
sum[node<<1]+=lazy2[node];
sum[node<<1|1]+=lazy2[node];
lazy2[node]=-1;
}
}
void insert1(int node,int l,int r,int x,int y,int k)
{
if(x<=l&&r<=y)
{
sum[node]=k;
lazy1[node]=k;
lazy2[node]=-1;
return ;
}
pushdown(node,l,r);
int mid=(l+r)>>1;
if(x<=mid) insert1(node<<1,l,mid,x,y,k);
if(y>mid) insert1(node<<1|1,mid+1,r,x,y,k);
update(node);
}
void insert2(int node,int l,int r,int x,int y,int k)
{
if(x<=l&&r<=y)
{
sum[node]+=k;
if(lazy1[node]!=-1) lazy1[node]=+k;
lazy2[node]+=k+(lazy2[node]==-1);
return ;
}
pushdown(node,l,r);
int mid=(l+r)>>1;
if(x<=mid) insert2(node<<1,l,mid,x,y,k);
if(y>mid) insert2(node<<1|1,mid+1,r,x,y,k);
update(node);
}
int query(int node,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return sum[node];
pushdown(node,l,r);
int mid=(l+r)>>1;
int cnt=0;
if(x<=mid) cnt=max(cnt,query(node<<1,l,mid,x,y));
if(y>mid) cnt=max(cnt,query(node<<1|1,mid+1,r,x,y));
return cnt;
}
void Cover(int u,int v,int w)
{
if(u==v) return;
while(top[u]!=top[v])
{
int tu=top[u];
int tv=top[v];
if(dep[tu]>dep[tv])
{
insert1(1,1,n,dfn[tu],dfn[u],w);
u=Fa[tu];
}
else
{
insert1(1,1,n,dfn[tv],dfn[v],w);
v=Fa[tv];
}
}
if(dep[u]<dep[v]) swap(u,v);
insert1(1,1,n,dfn[son[v]],dfn[u],w);
}
void Add(int u,int v,int w)
{
if(u==v) return ;
while(top[u]!=top[v])
{
int tu=top[u];
int tv=top[v];
if(dep[tu]>dep[tv])
{
insert2(1,1,n,dfn[tu],dfn[u],w);
u=Fa[tu];
}
else
{
insert2(1,1,n,dfn[tv],dfn[v],w);
v=Fa[tv];
}
}
if(dep[u]<dep[v]) swap(u,v);
insert2(1,1,n,dfn[son[v]],dfn[u],w);
}
int Max(int u,int v)
{
int cnt=0;
if(u==v) return cnt;
while(top[u]!=top[v])
{
int tu=top[u];
int tv=top[v];
if(dep[tu]>dep[tv])
{
cnt=max(cnt,query(1,1,n,dfn[tu],dfn[u]));
u=Fa[tu];
}
else
{
cnt=max(cnt,query(1,1,n,dfn[tv],dfn[v]));
v=Fa[tv];
}
}
if(dep[u]<dep[v]) swap(u,v);
cnt=max(cnt,query(1,1,n,dfn[son[v]],dfn[u]));
return cnt;
}
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read();
int v=read();
int w=read();
add(u,v,w);
add(v,u,w);
}
dfs1(1,0);dfs2(1,0);
build(1,1,n);
while(cin>>opt)
{
if(opt[1]=='t') break;
if(opt[1]=='h')
{
int x=read();int y=read();
int u=a[x<<1].from;int v=a[x<<1].to;
if(dep[u]>dep[v]) insert1(1,1,n,dfn[u],dfn[u],y);
else insert1(1,1,n,dfn[v],dfn[v],y);
}
if(opt[1]=='o')
{
int u=read();
int v=read();
int w=read();
Cover(u,v,w);
}
if(opt[1]=='d')
{
int u=read();
int v=read();
int w=read();
Add(u,v,w);
}
if(opt[1]=='a')
{
int u=read();
int v=read();
printf("%d\n",Max(u,v));
}
/*for(int i=1;i<=n;i++)
query(1,1,n,dfn[i],dfn[i]);*/
}
return 0;
}
15
1 10 19
2 9 39
3 12 3
4 12 21
5 1 23
6 5 91
7 10 80
8 1 93
9 4 50
10 9 41
11 4 66
13 5 85
14 15 50
15 2 54
Add 15 11 72
Add 5 9 64
Add 13 1 57
Max 8 7
Max 1 8
Add 1 8 44
Change 14 25
Change 11 33
Cover 6 12 45
Add 13 12 92
Cover 4 4 48
Add 10 3 55
Add 2 10 26
Change 13 34
Add 9 1 43
Cover 15 2 3
Cover 3 2 51
Max 10 14
Change 10 81
Cover 10 6 89
Stop
附加一组数据,上面的代码输出:
93
93
124
但如果把注释去掉,输出(正确结果):
93
93
261