火车头wordpress 4.6百度推广优化方案

题目大意

有一个有$n$个点$n$条边的无向连通图，一开始每条边都有一个颜色$c$。

有$m$次操作，每次操作将一条两个端点为$x,y$的边的颜色修改为$c$。求每次修改之后，图中有多少个颜色相同的连通块。

一个颜色相同的连通块指的是一个由一些相同颜色的边组成的连通块。

有$T$组数据。

$1\le T\le 10,3\le n,m\le 10^5,1\le c\le n$

题解

我们可以发现，这个图是一个基环树。

下面先考虑这个图是一棵树的情况。

我们考虑将一条边的修改看成给这条边删去颜色和给这条边加上颜色两个部分，那么一开始加边时处理边的颜色也可以看作给没有颜色的边加上颜色。

我们先考虑删去一条边的颜色对答案的贡献，设这条边的两个端点为$x,y$，颜色为$c$：

• 如果$x$有另外一条颜色为$c$的边，$y$也有，则删去这条边后，原本的这个连通块会变成两个连通块，答案加一
• 如果$x$有另外一条颜色为$c$的边，$y$没有，则删去这条边后，原本的这个连通块会少一个点$x$，答案不变
• 如果$x$没有另外一条颜色为$c$的边，$y$有，则删去这条边后，原本的这个连通块会少一个点$y$，答案不变
• 如果$x$没有另外一条颜色为$c$的边，$y$也没有，则删去这条边后，这个只由$x$和$y$构成的连通块就没了，答案减一

再考虑加上一条边的颜色对答案的贡献，设这条边的两个端点为$x,y$，颜色为$c$：

• 如果$x$有另外一条颜色为$c$的边，$y$也有，则加上这条边后，原本的这两个连通块会变成一个连通块，答案减一
• 如果$x$有另外一条颜色为$c$的边，$y$没有，则加上这条边后，原本的这个连通块会多一个点$y$，答案不变
• 如果$x$没有另外一条颜色为$c$的边，$y$有，则加上这条边后，原本的这个连通块会多一个点$x$，答案不变
• 如果$x$没有另外一条颜色为$c$的边，$y$也没有，则加上这条边后，就会构成一个只由$x$和$y$构成的连通块，答案加一

而当这个图是基环树的时候，有一些特殊情况需要特判：

• 如果边在环上，且环上的边的颜色都是$c$，则删去这条边后答案不变
• 如果边在环上，且环上除了这条边之外的边的颜色都是$c$，则加上这条边后答案不变

我们先找出环，然后按上面说的做就可以了。

注意在查找两个端点为$x,y$的边的编号和每个点是否有每种颜色的边的时候，可以用$map$来储存。

时间复杂度为$O(n\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int T,n,m,tot,d[2*N+5],l[2*N+5],r[N+5],c[N+5];
int ans,top,st[N+5],lp[N+5],dep[N+5],z[N+5],sum[N+5];
map<int,int>mp[N+5],hv[N+5];
struct node{int x,y,v;
}w[N+5];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u,int fa){dep[u]=dep[fa]+1;st[++top]=u;for(int i=r[u];i;i=l[i]){if(d[i]==fa) continue;if(dep[d[i]]&&dep[d[i]]<dep[u]){while(st[top]!=d[i]){lp[++lp[0]]=st[top];--top;}lp[++lp[0]]=d[i];}if(!dep[d[i]]) dfs(d[i],u);}if(st[top]==u) --top;
}
void pt(int x,int y,int v,int zt){int tmp=(hv[x][v]!=0)+(hv[y][v]!=0);++hv[x][v];++hv[y][v];if(zt) ++sum[v];if(zt&&sum[v]==lp[0]) --tmp;ans+=1-tmp;
}
void del(int x,int y,int v,int zt){--hv[x][v];--hv[y][v];int tmp=(hv[x][v]!=0)+(hv[y][v]!=0);if(zt&&sum[v]==lp[0]) --tmp;if(zt) --sum[v];ans-=1-tmp;
}
int main()
{freopen("tour.in","r",stdin);freopen("tour.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);tot=0;ans=0;for(int i=0;i<=N;i++){r[i]=dep[i]=z[i]=c[i]=sum[i]=0;mp[i].clear();hv[i].clear();}for(int i=1,x,y,v;i<=n;i++){scanf("%d%d%d",&x,&y,&v);w[i]=(node){x,y,v};add(x,y);add(y,x);mp[x][y]=mp[y][x]=i;}top=0;lp[0]=0;dfs(1,0);for(int i=1,x,y;i<=lp[0];i++){x=lp[i];y=lp[i%lp[0]+1];z[mp[x][y]]=1;}for(int i=1;i<=n;i++){pt(w[i].x,w[i].y,w[i].v,z[i]);c[i]=w[i].v;}for(int i=1,x,y,v,p;i<=m;i++){scanf("%d%d%d",&x,&y,&v);p=mp[x][y];del(x,y,c[p],z[p]);pt(x,y,v,z[p]);c[p]=v;printf("%d\n",ans);}}return 0;
}