更差的阅读体验
很简单的一道题，但是原来的翻译太唐了 /tuu
我们考虑离线，把边的优先级和询问的值均从大到小排序。这样我们只剩下加边操作。
操作有有以下三种情况：
- 将度数为 \(0\) 的点删除。这种操作会让点数 \(-1\) 并且不会影响到其他点的度数。
- 将度数为 \(2\) 的点的两个邻居之间链边并将这个点删除。这种操作会让点数、边数都 \(-1\) 并且不会影响到其他点的度数。
- 特别地，如果一个点是个自环，则经过一次操作 2 后点数和边数都不变。
我们只要找出有多少次 3 的情况就能算出最后剩几个点几条边了。
如果一个连通块有度数 $ \not = 2$ 的点，则这个点不管多少次操作都不会变。一个连通块会删除出自环，一定是这个连通块本身就是一个简单环。
我们写一个并查集，维护一个连通块的形态是否是链或简单环，如果是链，还要维护链的两个端点。一次合并的时候，如果是在两条链的端点出合并，那么会合并出一条更长的链。如果实在同一条链的两个端点处合并，那么就会合并处一个环。至于度数为 \(0\) 或 \(2\) 的点可以很简单在加边的过程中动态维护。
那么这道题就做完了，复杂度为 \(O(n \log n)\)。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 300006
using namespace std;
int n,m,m_now,q,c0,c2,deg[N],vertex[N],edge[N];
pair<int,int> ask[N];
struct Edge{int u,v,w;void read(){scanf("%lld%lld%lld",&u,&v,&w);}
}E[N];
struct Node{int is_chain,c1,c2;int is_ring;int fa;void init(int i){is_chain=1,c1=c2=fa=i,is_ring=0;}
}f[N];
struct UFS{int ring_cnt;void init(){for(int i=1;i<=n;i++)f[i].init(i);}int find(int k){return f[k].fa==k?k:f[k].fa=find(f[k].fa);}void merge(int u,int v){int fu=find(u),fv=find(v);if(fu!=fv){if(f[fu].is_chain&&f[fv].is_chain){f[fu].is_chain=0;if(f[fu].c1==u&&f[fv].c1==v)f[fu].is_chain=1,f[fu].c1=f[fu].c2,f[fu].c2=f[fv].c2;else if(f[fu].c1==u&&f[fv].c2==v)f[fu].is_chain=1,f[fu].c1=f[fu].c2,f[fu].c2=f[fv].c1;else if(f[fu].c2==u&&f[fv].c1==v)f[fu].is_chain=1,f[fu].c1=f[fu].c1,f[fu].c2=f[fv].c2;else if(f[fu].c2==u&&f[fv].c2==v)f[fu].is_chain=1,f[fu].c1=f[fu].c1,f[fu].c2=f[fv].c1;} else f[fu].is_chain=f[fv].is_chain=0;ring_cnt-=f[fu].is_ring,f[fu].is_ring=0;ring_cnt-=f[fv].is_ring,f[fv].is_ring=0;f[fv].fa=fu;} else {ring_cnt-=f[fu].is_ring,f[fu].is_ring=0;if(f[fu].is_chain){int mn_c=min(f[fu].c1,f[fv].c2),mx_c=max(f[fu].c1,f[fv].c2);int mn_uv=min(u,v),mx_uv=max(u,v);if(mn_c==mn_uv&&mx_c==mx_uv)f[fu].is_ring=1,ring_cnt++;}f[fu].is_chain=0;}}
}S;
void addedge(int u,int v)
{if(!deg[u])c0--;if(!deg[v])c0--;if(deg[u]==2)c2--;if(deg[v]==2)c2--;deg[u]++,deg[v]++,m_now++,S.merge(u,v);if(deg[u]==2)c2++;if(deg[v]==2)c2++;
}
main()
{scanf("%lld%lld",&n,&m),S.init(),c0=n;for(int i=1;i<=m;i++)E[i].read();sort(E+1,E+1+m,[](Edge x,Edge y){return x.w>y.w;});scanf("%lld",&q);for(int i=1;i<=q;i++)scanf("%lld",&ask[i].first),ask[i].second=i;sort(ask+1,ask+1+q,[](pair<int,int> x,pair<int,int> y){return x.first>y.first;});for(int i=1,j=0;i<=q;i++){while(j<m&&E[j+1].w>=ask[i].first)j++,addedge(E[j].u,E[j].v);vertex[ask[i].second]=n-c0-c2+S.ring_cnt,edge[ask[i].second]=m_now-c2+S.ring_cnt;}for(int i=1;i<=q;i++)printf("%lld %lld\n",vertex[i],edge[i]);return 0;
}