2023NOIP A层联测20-旅行

小 A 旅行到了远方的一座城市，其内部的道路可以被视为一张包含恰好 $n$ 个点以及 $n$ 条边的无向连通图。这里的居民可以用一种特质的墨水来改变图中某一条边的颜色。

居民们的狂欢节即将开始了，且节日会持续 $m$ 天。每一天，居民们会选择图中的一条边，并用某一种颜色的墨水去覆盖这条边原有的颜色。在每一天的最后，他们都想知道当前的城市包含多少个颜色相同的连通块。

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

多组数据 $T\le 10$
$n,m\le 10^5$

---

首先这个图是基环树。

可以用各种方法求出一开始颜色相同连通块的个数。我使用并查集。

对于每次询问，改变这条边的颜色，贡献只需看两个点的连边情况。

可以分成两部分考虑，先去掉这条边的颜色，再加上修改的颜色。

前一个操作，如果两边都有这种颜色，那么断掉这条边会增加一个连通块；如果两边都没有，就会减少一个；否则不变。

后一个操作，如果两边都有这种颜色，那么断掉这条边会减少一个连通块；如果两边都没有，就会增加一个；否则不变。

但是如果两边的颜色是同一个连通块，那么就不会增加连通块，这种情况只能是环上的边全是一种颜色（在后种情况就是除了当前边全是一种颜色），特判即可。

实现上可以开 $n$ 个 map 维护当前点的出边颜色。

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

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,m,fa[N],bj[N],dfn[N],low[N],num,vis[N],VIS[N];
stack<int> s;
vector<int> ans;
map<int,int> ma[N],ring;
map<pair<int,int>,int> To;
struct Node
{int v,w,id;Node(){}Node(int a,int b,int c){v=a,w=b,id=c;}
};
vector<Node> v[N];
struct node
{int u,v,w;bool operator==(const node &a)const{return u==a.u&&v==a.v&&w==a.w;}
}a[N];
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
void add(int x,int y)
{int a=find(x),b=find(y);if(a!=b) fa[a]=b;
}
void dfs(int u,int fa)
{dfn[u]=low[u]=++num;s.push(u);for(auto i:v[u]){if(!dfn[i.v]){dfs(i.v,u);low[u]=min(low[u],low[i.v]);if(low[i.v]>=dfn[u]){vector<int> aa;int x=0;do{x=s.top();s.pop();aa.push_back(x);}while(x!=i.v);aa.push_back(u);if(aa.size()>2) ans=aa;}}else if(i.v!=fa) low[u]=min(low[u],dfn[i.v]);}
}
void Dfs(int u,int fa)
{if(VIS[u]) return;VIS[u]=1;for(auto i:v[u]) if(i.v!=fa&&vis[i.v]) ring[i.w]++,Dfs(i.v,u);
}
int main()
{freopen("tour.in","r",stdin);freopen("tour.out","w",stdout);int t;cin>>t;while(t--){memset(VIS,0,sizeof(VIS));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));num=0;while(s.size()) s.pop();To.clear();ans.clear();ring.clear();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1,x,y,w;i<=n;i++){scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);if(a[i].u>a[i].v) swap(a[i].u,a[i].v);v[a[i].u].push_back(Node(a[i].v,a[i].w,i));v[a[i].v].push_back(Node(a[i].u,a[i].w,i));ma[a[i].u][a[i].w]++;ma[a[i].v][a[i].w]++;To[make_pair(a[i].u,a[i].v)]=i;}dfs(1,0);for(auto i:ans) vis[i]=1;if(ans.size()) for(auto i:v[ans.front()]) if(vis[i.v]){Dfs(ans.front(),i.v);break;}for(int i=1;i<=n;i++){for(auto j:v[a[i].u]){if(j.v==a[i].v) continue;if(j.w==a[i].w) add(i,j.id);}for(auto j:v[a[i].v]){if(j.v==a[i].u) continue;if(j.w==a[i].w) add(i,j.id);}}for(int i=1;i<=n;i++) bj[i]=find(i);sort(bj+1,bj+1+n);int num=unique(bj+1,bj+1+n)-bj-1;for(int i=1,x,y,w;i<=m;i++){scanf("%d%d%d",&x,&y,&w);if(x>y) swap(x,y);int id=To[make_pair(x,y)];int fl1=0,fl2=0;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;fl1=ma[a[id].u][a[id].w];fl2=ma[a[id].v][a[id].w];ma[a[id].u][a[id].w]++;ma[a[id].v][a[id].w]++;if(fl1&&fl2&&(!vis[a[id].u]||!vis[a[id].v]||ring.size()>1)) num++;else if(!fl1&&!fl2) num--;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;if(vis[a[id].u]&&vis[a[id].v]) ring[a[id].w]--;if(!ring.count(a[id].w)) ring.erase(a[id].w);if(!ma[a[id].u][a[id].w]) ma[a[id].u].erase(a[id].w);if(!ma[a[id].v][a[id].w]) ma[a[id].v].erase(a[id].w);a[id].w=w;ma[a[id].u][a[id].w]++;ma[a[id].v][a[id].w]++;if(vis[a[id].u]&&vis[a[id].v]) ring[a[id].w]++;fl1=0,fl2=0;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;fl1=ma[a[id].u][a[id].w];fl2=ma[a[id].v][a[id].w];ma[a[id].u][a[id].w]++;ma[a[id].v][a[id].w]++;if(vis[a[id].u]&&vis[a[id].v]){ring[a[id].w]--;if(!ring.count(a[id].w)) ring.erase(a[id].w);}if(fl1&&fl2&&(!vis[a[id].u]||!vis[a[id].v]||ring.size()>1)) num--;else if(!fl1&&!fl2) num++;if(vis[a[id].u]&&vis[a[id].v]) ring[a[id].w]++;printf("%d\n",num);}for(int i=1;i<=n;i++) v[i].clear(),ma[i].clear();}
}