2 条题解
-
0
C65【模板】线段树合并 P4556 [Vani有约会]雨天的尾巴
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int>G[N]; int dep[N],f[N][20],D; void dfs1(int x,int fa) { dep[x]=dep[fa]+1; f[x][0]=fa;for(int i=1;i<=D;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int y:G[x])if(y!=fa) dfs1(y,x); } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=D;i>=0;i--)if( dep[ f[x][i] ]>= dep[y]) x=f[x][i]; if(x==y) return x; for(int i=D;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } #define lc tr[p].ls #define rc tr[p].rs #define mid (l+r)/2 int u[N],v[N],c[N],b[N],ans[N],ln; struct trnode{int ls,rs,id,c;trnode(){id=c=0;}}tr[N*4*20];int trlen,rt[N]; void pushup(int p) { if(tr[lc].c>=tr[rc].c) tr[p].id=tr[lc].id,tr[p].c=tr[lc].c; else tr[p].id=tr[rc].id,tr[p].c=tr[rc].c; } void change(int &p,int l,int r,int x,int c) { if(p==0)p=++trlen; if(l==r){ tr[p].c+=c,tr[p].id=x;return ;} if(x<=mid)change(lc,l,mid,x,c); else change(rc,mid+1,r,x,c); pushup(p); } void merge(int &u1,int u2,int l,int r) { if(!u1||!u2) {u1|=u2;return ;} if(l==r) {tr[u1].c+=tr[u2].c;return ;} merge(tr[u1].ls,tr[u2].ls,l,mid); merge(tr[u1].rs,tr[u2].rs,mid+1,r); pushup(u1); } void dfs2(int x,int fa) { for(int y:G[x])if(y!=fa) { dfs2(y,x); merge(rt[x],rt[y],1,ln); } if(!tr[rt[x]].c) ans[x]=0; else ans[x]=tr[rt[x]].id; } int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); G[x].push_back(y);G[y].push_back(x); } D=log2(n);dep[0]=0;dfs1(1,0); for(int i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&c[i]);b[i]=c[i]; sort(b+1,b+1+m);ln=unique(b+1,b+1+m)-b-1; memset(rt,0,sizeof(rt));trlen=0; for(int i=1;i<=m;i++) { int p=LCA(u[i],v[i]),cc=lower_bound(b+1,b+ln+1,c[i])-b; change(rt[u[i]],1,ln,cc,1); change(rt[v[i]],1,ln,cc,1); change(rt[p],1,ln,cc,-1); change(rt[f[p][0]],1,ln,cc,-1); } b[0]=0;dfs2(1,0); for(int i=1;i<=n;i++) printf("%d\n",b[ans[i]]); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:08:07
C65【模板】线段树合并 P4556 [Vani有约会]雨天的尾巴
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int>G[N]; int dep[N],f[N][20],D; void dfs1(int x,int fa) { dep[x]=dep[fa]+1; f[x][0]=fa;for(int i=1;i<=D;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int y:G[x])if(y!=fa) dfs1(y,x); } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=D;i>=0;i--)if( dep[ f[x][i] ]>= dep[y]) x=f[x][i]; if(x==y) return x; for(int i=D;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } #define lc tr[p].ls #define rc tr[p].rs #define mid (l+r)/2 int u[N],v[N],c[N],b[N],ans[N],ln; struct trnode{int ls,rs,id,c;trnode(){id=c=0;}}tr[N*4*20];int trlen,rt[N]; void pushup(int p) { if(tr[lc].c>=tr[rc].c) tr[p].id=tr[lc].id,tr[p].c=tr[lc].c; else tr[p].id=tr[rc].id,tr[p].c=tr[rc].c; } void change(int &p,int l,int r,int x,int c) { if(p==0)p=++trlen; if(l==r){ tr[p].c+=c,tr[p].id=x;return ;} if(x<=mid)change(lc,l,mid,x,c); else change(rc,mid+1,r,x,c); pushup(p); } void merge(int &u1,int u2,int l,int r) { if(!u1||!u2) {u1|=u2;return ;} if(l==r) {tr[u1].c+=tr[u2].c;return ;} merge(tr[u1].ls,tr[u2].ls,l,mid); merge(tr[u1].rs,tr[u2].rs,mid+1,r); pushup(u1); } void dfs2(int x,int fa) { for(int y:G[x])if(y!=fa) { dfs2(y,x); merge(rt[x],rt[y],1,ln); } if(!tr[rt[x]].c) ans[x]=0; else ans[x]=tr[rt[x]].id; } int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); G[x].push_back(y);G[y].push_back(x); } D=log2(n);dep[0]=0;dfs1(1,0); for(int i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&c[i]),b[i]=c[i]; sort(b+1,b+1+m);ln=unique(b+1,b+1+m)-b-1; memset(rt,0,sizeof(rt));trlen=0; for(int i=1;i<=m;i++) { int p=LCA(u[i],v[i]),cc=lower_bound(b+1,b+ln+1,c[i])-b; change(rt[u[i]],1,ln,cc,1); change(rt[v[i]],1,ln,cc,1); change(rt[p],1,ln,cc,-1); change(rt[f[p][0]],1,ln,cc,-1); } b[0]=0;dfs2(1,0); for(int i=1;i<=n;i++) printf("%d\n",b[ans[i]]); return 0; }
- 1
