AGC 014 B – Unplanned Queries

题面在这里！

很显然的一件事是，我们把路径覆盖改成两个点分别到根的路径覆盖，答案是不会变的，因为lca以上被覆盖了两次不变奇偶性。。

这么做的好处就是，我们只需要考虑每个点的覆盖次数带来的影响就行了，也就是不用考虑每次覆盖的两个点的关系。

发现点 x （除了根）到它父亲 fa  的边 (x,fa) 被覆盖了 sum[x]次，其中sum[x]是指x子树中所有点被覆盖次数的和，显然sum[x]必须是偶数才行。

又因为偶数具有传递性，也就是一个点x所有儿子的sum都是偶数满足条件的话，必须x被操作的次数也是偶数才行。

当然根可以不需要满足sum是偶数，所以被覆盖次数是奇数的点不能>1.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;inline int read(){
int x=0; char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}int n,d[N],cnt,m;int main(){
n=read(),m=read();
while(m--) d[read()]^=1,d[read()]^=1;
for(int i=1;i<=n;cnt+=d[i],i++) if(cnt&d[i]){ puts("NO"); return 0;}
puts("YES");
return 0;
}