题意：给你一颗树，每次选择一条简单路径进行染色，问最后每条边的颜色
此题非常之坑，各种卡，主要是卡栈空间
首先看题就写了个树剖，让后各种TLE和RE，开了O3还是不行
#pragma GCC opitmize("O3")#pragma G++ opitmize("O3")#pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #define N 500010using namespace std;struct Edge{ int v,nt; } G[N];int h[N],d[N],top[N],sz[N],son[N];int f[N],w[N],v[N<<2],n,m,cnt=0,clk=0;inline void adj(int x,int y){ G[++cnt]=(Edge){y,h[x]}; h[x]=cnt; }inline void pd(int x){ if(v[x]) v[x<<1]=v[x<<1|1]=v[x]; v[x]=0; }void dfs(int x){ d[x]=d[f[x]]+1; sz[x]=1; for(int v,i=h[x];i;i=G[i].nt){ dfs(v=G[i].v); sz[x]+=sz[v]; if(sz[v]>sz[son[x]]) son[x]=v; }}void dt(int x,int p){ w[x]=++clk; top[x]=p; if(son[x]) dt(son[x],p); for(int v,i=h[x];i;i=G[i].nt) if((v=G[i].v)!=son[x]) dt(v,v);}void update(int l,int r,int x,int L,int R,int k){ if(L<=l && r<=R){ v[x]=k; return; } pd(x); int m=l+r>>1; if(L<=m) update(l,m,x<<1,L,R,k); if(m >1; if(k<=m) return gAns(l,m,x<<1,k); else return gAns(m+1,r,x<<1|1,k);}void gLca(int x,int y,int c){ for(;top[x]!=top[y];y=f[top[y]]){ if(d[top[x]]>d[top[y]]) swap(x,y); update(1,n,1,w[top[y]],w[y],c); } if(d[x]>d[y]) swap(x,y); if(x!=y) update(1,n,1,w[x]+1,w[y],c);}int main(){ scanf("%d%d",&n,&m); for(int x,i=2;i<=n;++i){ scanf("%d",&x); adj(x,i); f[i]=x; } dfs(1); dt(1,1); for(int x,y,c;m--;){ scanf("%d%d%d",&x,&y,&c); gLca(x,y,c); } for(int i=2;i<=n;++i) printf("%d\n",gAns(1,n,1,w[i]));} 数据范围有50W！树剖肯定卡不过去了，看正解 正解是：dsu+离线倒序处理，每次染色过后，将该路径上面的点缩成一个并不再访问
恶魔妈妈摸妹妹，好吧写了一发
#include#include #include #define N 500010using namespace std;int f[N],p[N],s[N][4],n,m,d[N],A[N],cnt=0;int h1[N],nt1[N],h2[N<<1],nt2[N<<1],v[N<<1],w[N<<1];inline int gf(int x){ return f[x]?f[x]=gf(f[x]):x;}inline void adj(int x,int y,int c){ v[++cnt]=y; w[cnt]=c; nt2[cnt]=h2[x]; h2[x]=cnt;}void gLca(int x){ d[x]=d[p[x]]+1; for(;h2[x];h2[x]=nt2[h2[x]]) s[w[h2[x]]][0]=gf(v[h2[x]]); for(;h1[x];h1[x]=nt1[h1[x]]) gLca(h1[x]); f[x]=p[x];}void cover(int g,int x,int c){ for(x=gf(x);d[x]>d[g];x=gf(f[x]=p[x])) A[x]=c;}int main(){ scanf("%d%d",&n,&m); for(int i=2;i<=n;++i) scanf("%d",p+i),nt1[i]=h1[p[i]],h1[p[i]]=i; for(int i=1;i<=m;++i){ scanf("%d%d%d",s[i]+1,s[i]+2,s[i]+3); adj(s[i][1],s[i][2],i); adj(s[i][2],s[i][1],i); } gLca(1); memset(f,0,sizeof f); for(;m;--m){ cover(s[m][0],s[m][1],s[m][3]); cover(s[m][0],s[m][2],s[m][3]); } for(int i=2;i<=n;++i) printf("%d\n",A[i]);}
80pts，dfs算lca的时候爆栈了！
最后把dfs改成了bfs才过。。。。。
#pragma GCC opitmize("O2")#pragma G++ opitmize("O2")#include #include #include #include #define N 500010using namespace std;int f[N],p[N],s[N][4],n,m,d[N],A[N],cnt=0,h[N],nt[N];int gf(int x){ return f[x]?f[x]=gf(f[x]):x;}void gDep(){ queue q; q.push(d[1]=1); for(int x;!q.empty();q.pop()){ x=q.front(); for(;h[x];h[x]=nt[h[x]]){ d[h[x]]=d[x]+1; q.push(h[x]); } }}void cover(int x,int y,int c){ for(x=gf(x),y=gf(y);x!=y;x=gf(f[x]=p[x])){ if(d[x] 实在是坑，但是代码一次次短，emmmmmmmmm。