2 条题解
-
0
#include<cstdio> #include<cstring> #include<algorithm> #define ri register int using namespace std; char ch[10]; int n,m,x,y,tot,cnt=0,root[100010],w[100010],c[100010]; struct tree{int s,c,ls,rs;}tr[3400000]; int len,last[100010]; struct edge{int x,y,next;}a[200010]; int fa[100010],size[100010],dep[100010],son[100010],top[100010],id[100010]; inline void add(int &now){now=++cnt;} inline void pushup(int now) { int ls=tr[now].ls,rs=tr[now].rs; tr[now].s=tr[ls].s+tr[rs].s; tr[now].c=max(tr[ls].c,tr[rs].c); } inline void update(int ul,int ur,int k,int &now,int l,int r) { if(!now) add(now); if(ul<=l&&r<=ur){tr[now].s=(r-l+1)*k;tr[now].c=k;return;} int mid=(l+r)>>1; if(ul<=mid) update(ul,ur,k,tr[now].ls,l,mid); if(ur>mid) update(ul,ur,k,tr[now].rs,mid+1,r); pushup(now); } inline int query_sum(int ql,int qr,int &now,int l,int r) { if(!now) return 0; if(ql<=l&&r<=qr) return tr[now].s; int mid=(l+r)>>1,res=0; if(ql<=mid) res+=query_sum(ql,qr,tr[now].ls,l,mid); if(qr>mid) res+=query_sum(ql,qr,tr[now].rs,mid+1,r); return res; } inline int query_max(int ql,int qr,int &now,int l,int r) { if(!now) return 0; if(ql<=l&&r<=qr) return tr[now].c; int mid=(l+r)>>1,res=0; if(ql<=mid) res=max(res,query_max(ql,qr,tr[now].ls,l,mid)); if(qr>mid) res=max(res,query_max(ql,qr,tr[now].rs,mid+1,r)); return res; } inline void add(int x,int y) { len++; a[len].x=x,a[len].y=y; a[len].next=last[x],last[x]=len; } void dfs1(int x,int f) { fa[x]=f,dep[x]=dep[f]+1,size[x]=1,son[x]=0; for(ri i=last[x];i;i=a[i].next) { int y=a[i].y; if(y!=fa[x]) { dfs1(y,x); if(size[y]>size[son[x]]) son[x]=y; size[x]+=size[y]; } } } void dfs2(int x,int tp) { id[x]=++tot,top[x]=tp; if(son[x]) dfs2(son[x],tp); for(ri i=last[x];i;i=a[i].next) { int y=a[i].y; if(y!=fa[x]&&y!=son[x]) dfs2(y,y); } } int solve(int x,int y,int rel,int op) { int tx=top[x],ty=top[y],ans=0; while(tx!=ty) { if(dep[tx]>dep[ty]) swap(x,y),swap(tx,ty); if(op==0) ans+=query_sum(id[ty],id[y],root[rel],1,n); else ans=max(ans,query_max(id[ty],id[y],root[rel],1,n)); y=fa[ty],ty=top[y]; } if(dep[x]>dep[y]) swap(x,y); if(op==0) ans+=query_sum(id[x],id[y],root[rel],1,n); else ans=max(ans,query_max(id[x],id[y],root[rel],1,n)); return ans; } int main() { scanf("%d %d",&n,&m); for(ri i=1;i<=n;i++) scanf("%d %d",&w[i],&c[i]); for(ri i=1;i<=n-1;i++) { scanf("%d %d",&x,&y); add(x,y),add(y,x); } dep[0]=0; dfs1(1,0); tot=0; dfs2(1,1); for(ri i=1;i<=n;i++) update(id[i],id[i],w[i],root[c[i]],1,n); for(ri i=1;i<=m;i++) { scanf("%s %d %d",ch+1,&x,&y); if(ch[2]=='C') update(id[x],id[x],0,root[c[x]],1,n),c[x]=y,update(id[x],id[x],w[x],root[c[x]],1,n); if(ch[2]=='W') w[x]=y,update(id[x],id[x],y,root[c[x]],1,n); if(ch[2]=='S') printf("%d\n",solve(x,y,c[x],0)); if(ch[2]=='M') printf("%d\n",solve(x,y,c[x],1)); } return 0; }#include<cstdio> #include<cstring> using namespace std; #define TP template<typename T> #define TP_ template<typename T,typename ... T_> TP void read(T &x) { x=0;int f=0;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar())ch=='-'&&(f=1); for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);f&&(x=-x); } TP_ void read(T &x,T_&...y){read(x);read(y...);} TP void write(T x){x<0&&(putchar('-'),x=-x);static int sta[35];int top=0;do{sta[++top]=x%10,x/=10;}while(x);while(top)putchar(sta[top--]^48);} TP void writeln(const T x){write(x);puts("");} TP void writesp(const T x){write(x);putchar(32);} TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);} using LL=long long; constexpr int N=1e5+5; struct edge{int y,pre;}a[N<<1];int alen,last[N]; void ins(int x,int y){a[++alen]={y,last[x]};last[x]=alen;} int max(const int &x,const int &y){return x>y?x:y;} void swap(int &x,int &y){x^=y^=x^=y;} namespace Chain { struct trnode { int son,fa,dep,siz,dfn,top; }tr[N]; void prepare(int x,int fa) { tr[x]={0,fa,tr[fa].dep+1,1}; for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(y==fa)continue; prepare(y,x); tr[x].siz+=tr[y].siz; if(tr[tr[x].son].siz<tr[y].siz)tr[x].son=y; } } int num; void dfs_chain(int x,int tp) { tr[x].top=tp;tr[x].dfn=++num; if(tr[x].son)dfs_chain(tr[x].son,tp); for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(y==tr[x].fa||y==tr[x].son)continue; dfs_chain(y,y); } } } namespace Segtree { struct trnode { int lc,rc;int sum,mx; }tr[N<<5]; int trlen,rt[N]; #define lc(x) tr[x].lc #define rc(x) tr[x].rc void pushup(int now) { tr[now].sum=tr[lc(now)].sum+tr[rc(now)].sum; tr[now].mx=max(tr[lc(now)].mx,tr[rc(now)].mx); } void modify(int &now,int x,int L,int R,int c) { if(!now)now=++trlen; if(L==R)tr[now].sum=tr[now].mx=c; else { int mid=(L+R)>>1; if(x<=mid)modify(lc(now),x,L,mid,c); if(x>=mid+1)modify(rc(now),x,mid+1,R,c); pushup(now); } } int query_sum(int now,int l,int r,int L,int R) { if(!now)return 0; if(l<=L&&R<=r)return tr[now].sum; int mid=(L+R)>>1,ans=0; if(l<=mid)ans+=query_sum(lc(now),l,r,L,mid); if(r>=mid+1)ans+=query_sum(rc(now),l,r,mid+1,R); return ans; } int query_mx(int now,int l,int r,int L,int R) { if(!now)return -1; if(l<=L&&R<=r)return tr[now].mx; int mid=(L+R)>>1,ans=0; if(l<=mid)ans=max(ans,query_mx(lc(now),l,r,L,mid)); if(r>=mid+1)ans=max(ans,query_mx(rc(now),l,r,mid+1,R)); return ans; } } int w[N],c[N]; int n; int query_sum(int x,int y) { int ans=0,bel=c[x]; using namespace Chain;using Segtree::rt; while(tr[x].top!=tr[y].top) { if(tr[tr[x].top].dep>tr[tr[y].top].dep)swap(x,y); ans+=Segtree::query_sum(rt[bel],tr[tr[y].top].dfn,tr[y].dfn,1,n); y=tr[tr[y].top].fa; } if(tr[x].dep>tr[y].dep)swap(x,y); ans+=Segtree::query_sum(rt[bel],tr[x].dfn,tr[y].dfn,1,n); return ans; } int query_mx(int x,int y) { int ans=0,bel=c[x]; using namespace Chain;using Segtree::rt;Segtree::query_mx(rt[0],1,1,1,n); while(tr[x].top!=tr[y].top) { if(tr[tr[x].top].dep>tr[tr[y].top].dep)swap(x,y); ans=max(ans,Segtree::query_mx(rt[bel],tr[tr[y].top].dfn,tr[y].dfn,1,n)); y=tr[tr[y].top].fa; } if(tr[x].dep>tr[y].dep)swap(x,y); ans=max(ans,Segtree::query_mx(rt[bel],tr[x].dfn,tr[y].dfn,1,n));return ans; } int main() { using namespace Chain;using Segtree::rt;using Segtree::modify; int q;read(n,q); for(int i=1;i<=n;i++)read(w[i],c[i]); for(int i=1,x,y;i<n;i++)read(x,y),ins(x,y),ins(y,x); prepare(1,0);dfs_chain(1,1); for(int i=1;i<=n;i++)modify(rt[c[i]],tr[i].dfn,1,n,w[i]); while(q--) { char op[5];scanf("%s",op); if(op[1]=='C') { int x;read(x); modify(rt[c[x]],tr[x].dfn,1,n,0); read(c[x]); modify(rt[c[x]],tr[x].dfn,1,n,w[x]); } else if(op[1]=='W') { int x;read(x);read(w[x]);modify(rt[c[x]],tr[x].dfn,1,n,w[x]); } else if(op[1]=='S') { int x,y;read(x,y);writeln(query_sum(x,y)); } else {int x,y;read(x,y);writeln(query_mx(x,y));} } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:08:33
#include<cstdio> #include<cstring> #include<algorithm> #define ri register int using namespace std; char ch[10]; int n,m,x,y,tot,cnt=0,root[100010],w[100010],c[100010]; struct tree{int s,c,ls,rs;}tr[3400000]; int len,last[100010]; struct edge{int x,y,next;}a[200010]; int fa[100010],size[100010],dep[100010],son[100010],top[100010],id[100010]; inline void add(int &now){now=++cnt;} inline void pushup(int now) { int ls=tr[now].ls,rs=tr[now].rs; tr[now].s=tr[ls].s+tr[rs].s; tr[now].c=max(tr[ls].c,tr[rs].c); } inline void update(int ul,int ur,int k,int &now,int l,int r) { if(!now) add(now); if(ul<=l&&r<=ur){tr[now].s=(r-l+1)*k,tr[now].c=k;return;} int mid=(l+r)>>1; if(ul<=mid) update(ul,ur,k,tr[now].ls,l,mid); if(ur>mid) update(ul,ur,k,tr[now].rs,mid+1,r); pushup(now); } inline int query_sum(int ql,int qr,int &now,int l,int r) { if(!now) return 0; if(ql<=l&&r<=qr) return tr[now].s; int mid=(l+r)>>1,res=0; if(ql<=mid) res+=query_sum(ql,qr,tr[now].ls,l,mid); if(qr>mid) res+=query_sum(ql,qr,tr[now].rs,mid+1,r); return res; } inline int query_max(int ql,int qr,int &now,int l,int r) { if(!now) return 0; if(ql<=l&&r<=qr) return tr[now].c; int mid=(l+r)>>1,res=0; if(ql<=mid) res=max(res,query_max(ql,qr,tr[now].ls,l,mid)); if(qr>mid) res=max(res,query_max(ql,qr,tr[now].rs,mid+1,r)); return res; } inline void add(int x,int y) { len++; a[len].x=x,a[len].y=y; a[len].next=last[x],last[x]=len; } void dfs1(int x,int f) { fa[x]=f,dep[x]=dep[f]+1,size[x]=1,son[x]=0; for(ri i=last[x];i;i=a[i].next) { int y=a[i].y; if(y!=fa[x]) { dfs1(y,x); if(size[y]>size[son[x]]) son[x]=y; size[x]+=size[y]; } } } void dfs2(int x,int tp) { id[x]=++tot,top[x]=tp; if(son[x]) dfs2(son[x],tp); for(ri i=last[x];i;i=a[i].next) { int y=a[i].y; if(y!=fa[x]&&y!=son[x]) dfs2(y,y); } } int solve(int x,int y,int rel,int op) { int tx=top[x],ty=top[y],ans=0; while(tx!=ty) { if(dep[tx]>dep[ty]) swap(x,y),swap(tx,ty); if(op==0) ans+=query_sum(id[ty],id[y],root[rel],1,n); else ans=max(ans,query_max(id[ty],id[y],root[rel],1,n)); y=fa[ty],ty=top[y]; } if(dep[x]>dep[y]) swap(x,y); if(op==0) ans+=query_sum(id[x],id[y],root[rel],1,n); else ans=max(ans,query_max(id[x],id[y],root[rel],1,n)); return ans; } int main() { scanf("%d %d",&n,&m); for(ri i=1;i<=n;i++) scanf("%d %d",&w[i],&c[i]); for(ri i=1;i<=n-1;i++) { scanf("%d %d",&x,&y); add(x,y),add(y,x); } dep[0]=0; dfs1(1,0); tot=0; dfs2(1,1); for(ri i=1;i<=n;i++) update(id[i],id[i],w[i],root[c[i]],1,n); for(ri i=1;i<=m;i++) { scanf("%s %d %d",ch+1,&x,&y); if(ch[2]=='C') update(id[x],id[x],0,root[c[x]],1,n),c[x]=y,update(id[x],id[x],w[x],root[c[x]],1,n); if(ch[2]=='W') w[x]=y,update(id[x],id[x],y,root[c[x]],1,n); if(ch[2]=='S') printf("%d\n",solve(x,y,c[x],0)); if(ch[2]=='M') printf("%d\n",solve(x,y,c[x],1)); } return 0; }
可能更好的代码：#include<cstdio> #include<cstring> using namespace std; #define TP template<typename T> #define TP_ template<typename T,typename ... T_> TP void read(T &x) { x=0;int f=0;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar())ch=='-'&&(f=1); for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48); f&&(x=-x); } TP_ void read(T &x,T_&...y){read(x);read(y...);} TP void write(T x){x<0&&(putchar('-'),x=-x);static int sta[35];int top=0;do{sta[++top]=x%10,x/=10;}while(x);while(top)putchar(sta[top--]^48);} TP void writeln(const T x){write(x);puts("");} TP void writesp(const T x){write(x);putchar(32);} TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);} using LL=long long; constexpr int N=1e5+5; struct edge{int y,pre;}a[N<<1];int alen,last[N]; void ins(int x,int y){a[++alen]=edge{y,last[x]};last[x]=alen;} int max(const int &x,const int &y){return x>y?x:y;} void swap(int &x,int &y){x^=y^=x^=y;} namespace Chain { struct trnode { int son,fa,dep,siz,dfn,top; }tr[N]; void prepare(int x,int fa) { tr[x]={0,fa,tr[fa].dep+1,1}; for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(y==fa) continue; prepare(y,x); tr[x].siz+=tr[y].siz; if(tr[tr[x].son].siz<tr[y].siz) tr[x].son=y; } } int num; void dfs_chain(int x,int tp) { tr[x].top=tp; tr[x].dfn=++num; if(tr[x].son)dfs_chain(tr[x].son,tp); for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(y==tr[x].fa||y==tr[x].son) continue; dfs_chain(y,y); } } } namespace Segtree { struct trnode { int lc,rc; int sum,mx; }tr[N<<5]; int trlen,rt[N]; #define lc(x) tr[x].lc #define rc(x) tr[x].rc void pushup(int now) { tr[now].sum=tr[lc(now)].sum+tr[rc(now)].sum; tr[now].mx=max(tr[lc(now)].mx,tr[rc(now)].mx); } void modify(int &now,int x,int L,int R,int c) { if(!now) now=++trlen; if(L==R) tr[now].sum=tr[now].mx=c; else { int mid=(L+R)>>1; if(x<=mid) modify(lc(now),x,L,mid,c); if(x>=mid+1) modify(rc(now),x,mid+1,R,c); pushup(now); } } int query_sum(int now,int l,int r,int L,int R) { if(!now)return 0; if(l<=L&&R<=r) return tr[now].sum; int mid=(L+R)>>1; int ans=0; if(l<=mid) ans+=query_sum(lc(now),l,r,L,mid); if(r>=mid+1) ans+=query_sum(rc(now),l,r,mid+1,R); return ans; } int query_mx(int now,int l,int r,int L,int R) { if(!now)return -1; if(l<=L&&R<=r) return tr[now].mx; int mid=(L+R)>>1; int ans=0; if(l<=mid) ans=max(ans,query_mx(lc(now),l,r,L,mid)); if(r>=mid+1) ans=max(ans,query_mx(rc(now),l,r,mid+1,R)); return ans; } } int w[N],c[N]; int n; int query_sum(int x,int y) { int ans=0,bel=c[x]; using namespace Chain; using Segtree::rt; while(tr[x].top!=tr[y].top) { if(tr[tr[x].top].dep>tr[tr[y].top].dep) swap(x,y); ans+=Segtree::query_sum(rt[bel],tr[tr[y].top].dfn,tr[y].dfn,1,n); y=tr[tr[y].top].fa; } if(tr[x].dep>tr[y].dep) swap(x,y); ans+=Segtree::query_sum(rt[bel],tr[x].dfn,tr[y].dfn,1,n); return ans; } int query_mx(int x,int y) { int ans=0,bel=c[x]; using namespace Chain; using Segtree::rt; while(tr[x].top!=tr[y].top) { if(tr[tr[x].top].dep>tr[tr[y].top].dep) swap(x,y); ans=max(ans,Segtree::query_mx(rt[bel],tr[tr[y].top].dfn,tr[y].dfn,1,n)); y=tr[tr[y].top].fa; } if(tr[x].dep>tr[y].dep) swap(x,y); ans=max(ans,Segtree::query_mx(rt[bel],tr[x].dfn,tr[y].dfn,1,n)); return ans; } int main() { using namespace Chain; using Segtree::rt; using Segtree::modify; int q; read(n,q); for(int i=1;i<=n;i++) read(w[i],c[i]); for(int i=1,x,y;i<n;i++) read(x,y),ins(x,y),ins(y,x); prepare(1,0); dfs_chain(1,1); for(int i=1;i<=n;i++) modify(rt[c[i]],tr[i].dfn,1,n,w[i]); while(q--) { char op[5];scanf("%s",op); if(op[1]=='C') { int x;read(x); modify(rt[c[x]],tr[x].dfn,1,n,0); read(c[x]); modify(rt[c[x]],tr[x].dfn,1,n,w[x]); } else if(op[1]=='W') { int x;read(x);read(w[x]); modify(rt[c[x]],tr[x].dfn,1,n,w[x]); } else if(op[1]=='S') { int x,y; read(x,y); writeln(query_sum(x,y)); } else { int x,y; read(x,y); writeln(query_mx(x,y)); } } return 0; }
- 1
