【题解】 CF891C Envy
很好玩的一道题。尽管不难，但是调了很久QAQ
考虑克鲁斯卡尔最小生成树的算法，可以发现这些最小树生成的性质：
-
当生成树所有边的权值都(le)某个$ w$的时刻，点的连通性是确定的。
-
只要是同一个图的最小生成树，记(f(w))是权值为(w)的边在最小树中生成次数，(f(w))是确定的。
实际上这就是一个拟阵的基本性质
但是做这道题我个人认为只需要考虑第一个性质就好了。
分析克鲁斯卡尔究竟在干嘛，是不是它就是在"不联通的就连上边，联通的就算了"，这样的最终结果都是两个点成功联通了。
再考虑克鲁斯卡尔的顺序，发现点联通的顺序是不变的，因为是按照(e[t].w)升序的。
再仔细分析一下克鲁斯卡尔到底在干嘛，是不是对于当前选中边的两个端点，假若联通就丢弃这条边，不联通就选取这条边。
考虑克鲁斯卡尔的性质，我们就记录一下对于一条边，当所有(le w)的边加入后,两端点的联通情况。
查询是问给定一个边集，是否可以得到一个包括所有这些边的MST
那么我们把边集按照(w)分类，每个(w)单独判断是否合法就好了。
怎么判断是否合法呢？不选取的条件就是两个端点不能联通，我们在主函数里预处理一下所有(w)的联通情况，（们只需记录端点在不在一起），那么查询这些边是否构成环就好了。
怎么判环？并查集。但是并查集初始化(O(n))，会(O(mn)TLE)。不会持久化结构，但是有个(tirck) ，就是我们只初始化我们要用的点，这样的正确性也很显然。
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
#define ERP(t,a) for(register int& t=head[a];t;t=e[t].nx)
#define midd register int mid=(l+r)>>1
#define TMP template < class ccf >
#define lef l,mid,pos<<1
#define rgt mid+1,r,pos<<1|1
#define pushup(pos) (seg[pos]=seg[pos<<1]+seg[pos<<1|1])
TMP inline ccf qr(ccf b){
register char c=getchar();register int q=1;register ccf x=0;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;}
TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}
TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}
TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}
TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}
TMP inline ccf Abs(ccf a){return a<0?-a:a;}
TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}
//----------------------template&IO---------------------------
const int maxn=1e5+15;
struct E{
int to,nx,id;
}e[maxn<<2];
int head[maxn];
int dfn[maxn<<1];
int ind[maxn];
int oud[maxn];
bool usd[maxn<<1];
int n,m;
int cnt;
int top;
inline void add(int fr,int to,int id,bool f){
e[++cnt]=(E){to,head[fr],id};head[fr]=cnt;
if(f) add(to,fr,-id,0);
}
void dfs(int now){
ERP(t,now){
register int qaq=t;
if(usd[abs(e[qaq].id)]) continue;
usd[abs(e[qaq].id)]=1;
dfs(e[qaq].to);
dfn[++top]=e[qaq].id;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
register int t1=qr(1)&1;
n=qr(1);m=qr(1);
for(register int t=1,r1,r2;t<=m;++t){
r1=qr(1);r2=qr(1);
add(r1,r2,t,t1);
++oud[r1];++ind[r2];
}
if(t1) {RP(t,1,n) if((ind[t]+oud[t])&1) return puts("NO"),0;}
else {RP(t,1,n) if(ind[t]^oud[t]) return puts("NO"),0; }
RP(t,1,n) if(head[t]) {dfs(t);if(top^m) return puts("NO"),0;break;}
puts("YES");
DRP(t,m,1) printf("%d ",dfn[t]);
putchar('
');
return 0;
}