社区讨论
萌新刚学oi,这道题全wa,求dalao帮助
P4315月下“毛景树”参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lobmruur
- 此快照首次捕获于
- 2023/10/29 23:33 2 年前
- 此快照最后确认于
- 2023/11/04 04:22 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int first[N],nxt[N<<1],to[N<<1],wei[N<<1],cnt;
inline void addedge(int u,int v,int w){
nxt[++cnt]=first[u];first[u]=cnt;
to[cnt]=v;wei[cnt]=w;
}
struct edge{
int u,v,w;
}e[N];
int n,m;
int hson[N],siz[N],dep[N],fa[N],val[N];
void dfs1(int u,int f){
fa[u]=f;siz[u]=1;
for(int i=first[u];i;i=nxt[i]){
int v=to[i],w=wei[i];
if(v==f) continue;
dep[v]=dep[u]+1;
val[v]=w;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]]) hson[u]=v;
}
}
int top[N],st[N],pre[N],tot;
void dfs2(int u,int tp){
// cout<<u<<' '<<tp<<endl;
top[u]=tp;st[u]=++tot;pre[tot]=u;
if(hson[u]) dfs2(hson[u],tp);
for(int i=first[u];i;i=nxt[i])
if(to[i]!=fa[u]&&to[i]!=hson[u])
dfs2(to[i],to[i]);
}
#define lc p<<1
#define rc p<<1|1
struct node{
int maxn,lazy1,lazy2;
}t[N<<2];
inline void pushup(int p){
return void(t[p].maxn=max(t[lc].maxn,t[rc].maxn));
}
inline void pushnow1(int p,int v){
t[p].lazy1=v;t[p].lazy2=0;
t[p].maxn=v;
}
inline void pushnow2(int p,int v){
if(t[p].lazy1){
t[p].lazy1+=v;t[p].maxn+=v;
}
else t[p].maxn+=v,t[p].lazy2+=v;
}
inline void pushdown(int p){
if(t[p].lazy1){
pushnow1(lc,t[p].lazy1);
pushnow1(rc,t[p].lazy1);
t[p].lazy1=0;
}
if(t[p].lazy2){
pushnow2(lc,t[p].lazy2);
pushnow2(rc,t[p].lazy2);
t[p].lazy2=0;
}
}
inline void build(int p,int l,int r){
if(l==r) return void(t[p].maxn=val[pre[l]]);
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
return pushup(p);
}
inline void change(int p,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr) return pushnow1(p,v);
pushdown(p);
int mid=l+r>>1;
if(ql<=mid) change(lc,l,mid,ql,qr,v);
if(qr>mid) change(rc,mid+1,r,ql,qr,v);
return pushup(p);
}
inline void add(int p,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr) return pushnow2(p,v);
pushdown(p);
int mid=l+r>>1;
if(ql<=mid) add(lc,l,mid,ql,qr,v);
if(qr>mid) add(rc,mid+1,r,ql,qr,v);
return pushup(p);
}
inline int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return t[p].maxn;
// cout<<"@#$$"<<t[p].maxn<<endl;
pushdown(p);
int mid=l+r>>1,ans=0;
if(ql<=mid) ans=max(ans,query(lc,l,mid,ql,qr));
if(qr>mid) ans=max(ans,query(rc,mid+1,r,ql,qr));
return ans;
}
inline void change(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,1,n,st[top[x]],st[x],v);
x=fa[top[x]];
}
if(x==y) return;
if(dep[x]>dep[y]) swap(x,y);
return change(1,1,n,st[x]+1,st[y],v);
}
inline void add(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(1,1,n,st[top[x]],st[x],v);
x=fa[top[x]];
}
if(x==y) return;
if(dep[x]>dep[y]) swap(x,y);
return add(1,1,n,st[x]+1,st[y],v);
}
inline int query(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,query(1,1,n,st[top[x]],st[x]));
x=fa[top[x]];
}
// cout<<"$%^&%^&";
// cout<<x<<' '<<y<<endl;
if(x==y) return ans;
if(dep[x]>dep[y]) swap(x,y);
ans=max(ans,query(1,1,n,st[x]+1,st[y]));
return ans;
}
inline int rd(){
char c=getchar();
int v=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') v=(v<<3)+(v<<1)+(c^48),c=getchar();
return v;
}
int main(){
n=rd();
for(int i=1;i<n;++i){
int u=rd(),v=rd(),w=rd();
e[i]=(edge){u,v,w};
addedge(u,v,w);addedge(v,u,w);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(1){
char c=getchar();
while(c<'A'||c>'Z') c=getchar();
if(c=='S') break;
if(c=='C'){
c=getchar();
if(c=='h') {int x=rd(),v=rd();change(1,1,n,dep[e[x].u]>dep[e[x].v]?st[e[x].u]:st[e[x].v],dep[e[x].u]>dep[e[x].v]?st[e[x].u]:st[e[x].v],v);}
else{int x=rd(),y=rd(),v=rd();change(x,y,v);}
}
else if(c=='A'){int x=rd(),y=rd(),v=rd();add(x,y,n);}
else {int x=rd(),y=rd();printf("%d\n",query(x,y));}
}
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...