実装はともかく、数え方は簡単。
https://codeforces.com/contest/1586/problem/E
問題
N頂点M辺のグラフが与えられる。各辺の重さの初期値は0とする。
ここに、Q個のクエリが与えられる。
各クエリiは頂点対(A[i],B[i])で指定される。
各クエリに対し、A[i]→B[i]となる単純パスを1つ選び、パス上の辺の重さを1増加させるとする。
全辺の重さを偶数とできるか判定し、できるならパスを答えよ。
解法
重さのパリティを考えると、複数のパスがあり得る場合、できるだけ複数のクエリで同じパスを通る方が良い。
そこで、全域木を1つ作り、その上でパスを考えよう。
全域木ならパスは一意に定まる。
int N,M,Q; template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; vector<int> E[303030]; int P[21][300005],D[300005]; void dfs(int cur) { FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs(e); } int getpar(int cur,int up) { int i; FOR(i,20) if(up&(1<<i)) cur=P[i][cur]; return cur; } int lca(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return (aa==bb)?aa:P[0][aa]; // vertex } UF<303030> uf; int num[303030]; int X[303030],Y[303030]; set<pair<int,int>> E2[303030]; vector<int> ret[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; x--,y--; if(uf[x]!=uf[y]) { E[x].push_back(y); E[y].push_back(x); uf(x,y); } } cin>>Q; FOR(i,Q) { cin>>X[i]>>Y[i]; X[i]--; Y[i]--; num[X[i]]++; num[Y[i]]++; } x=0; FOR(i,N) x+=num[i]%2; if(x) { cout<<"NO"<<endl; cout<<x/2<<endl; return; } dfs(0); FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]]; cout<<"YES"<<endl; FOR(i,Q) { int lc=lca(X[i],Y[i]); x=X[i]; y=Y[i]; vector<int> ret={x},ret2={y}; while(x!=lc) { x=P[0][x]; ret.push_back(x); } while(y!=lc) { y=P[0][y]; ret2.push_back(y); } ret2.pop_back(); reverse(ALL(ret2)); cout<<ret.size()+ret2.size()<<endl; FORR(a,ret) cout<<a+1<<" "; FORR(a,ret2) cout<<a+1<<" "; cout<<endl; } }
まとめ
本番もあんまり苦労してないな。