CF453C Little Pony and Summer Sun Celebration

题解

这道题要求输出任意解，并且路径长度不超过4n就行，所以给了我们乱搞构造的机会。

我这里给出一种构造思路：

首先一个连通块如果没有要求奇数次的点，那么就可以不管他，如果超过一个连通块内有要求奇数次的点，那么无解。

然后在那个唯一需要走的连通块里，我们随便抠一个生成树出来，从根遍历

---

①

首先把每次向下走以及回溯的路径记录到序列的新一位（并不需要一开始就把根节点加入，反正最后会回溯到根，于是最后一个元素添加为根），顺便记录奇偶性的变化，

这个过程增加的序列长度 <= 2n

②

然后在①的过程中，对于任意非根的点 i，当他要回溯到 fa[i] 时，如果他的次数奇偶性与我们想要的不同，那么在序列中加入一段“fa[i]，i”，这样就把 i 和 i 的子树都能调对，回溯后再考虑fa[i]，

这个过程增加的序列长度 <= 2n

③

在②的最后，回溯到根时，如果他的次数奇偶性不正确，就把序列最后一个元素（恰好就为根了吧）删掉，如果对于只有一个节点的情况，就在序列头加一个。

设个过程增加的序列长度在 -1 到 1 之间

---

可以证明，最终的序列长度不会超过4n。

C O D E

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define lowbit(x) ((-x)&(x))
using namespace std;
inline LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
    while(s >= '0' && s <= '9') {x = x * 10 + (s - '0');s = getchar();}
    return x * f;
}
int n,m,i,j,s,o,k,root;
vector<int> g[MAXN];
int fa[MAXN];
int findf(int x) {return fa[x] == x ? x:(fa[x] = findf(fa[x]));}
void unionSet(int x,int y) {fa[findf(x)] = findf(y);}
int c[MAXN],cnt;
bool f[MAXN];
int pr[MAXN*4],cnp;
int dfs(int x,int fa) {
    int res = c[x];
    f[x] = 1;
    for(int i = 0; i < g[x].size();i ++)  {
        if(g[x][i] != fa) {
            res = max(res,dfs(g[x][i],x));
        }
    }
    return res;
}
void dfs2(int x,int fa) {
    for(int i = 0; i < g[x].size();i ++)  {
        if(g[x][i] != fa) {
            pr[++ cnp] = g[x][i];
            c[g[x][i]] ^= 1;
            dfs2(g[x][i],x);
            pr[++ cnp] = x;
            c[x] ^= 1;
        }
    }
    if(fa) {
        if(c[x]) {
            pr[++ cnp] = fa;
            pr[++ cnp] = x;
            c[fa] ^= 1;
            c[x] ^= 1;
        }
    }
    else if(c[x]) {
        if(cnp > 0) cnp --;
        else pr[++ cnp] = x,c[x] ^= 1;
    }
    return ;
}
int main() {
    n = read();m = read();
    for(int i = 1;i <= n;i ++) fa[i] = i;
    for(int i = 1;i <= m;i ++) {
        s = read();o = read();
        if(findf(s) ^ findf(o))
            g[s].push_back(o),g[o].push_back(s),unionSet(s,o);
    }
    for(int i = 1;i <= n;i ++) c[i] = read();
    for(int i = 1;i <= n;i ++) {
        if(!f[i]) {
            int dt;
            cnt += (dt = dfs(i,0));
            if(dt) root = i;
        }
    }
    if(cnt > 1) {
        printf("-1\n");
        return 0;
    }
//    printf("cnt & root:%d %d\n",cnt,root);
    if(root) dfs2(root,0);
    printf("%d\n",cnp);
    for(int i = 1;i <= cnp;i ++) {
        printf("%d ",pr[i]);
    }ENDL;
    return 0;
}