1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN =100000+10;
struct edge{
    int to,nxt;
}ed[MAXN<<1];
int head[MAXN],cnt;
void addedge(int u,int v){
    ed[cnt].to=v;
    ed[cnt].nxt=head[u];
    head[u]=cnt++;
}
int sz[MAXN],ans;
void dfs(int u,int pre){
    sz[u]=1;
    for(int i=head[u];i!=-1;i=ed[i].nxt){
        int v=ed[i].to;
        if(v!=pre){
            dfs(v,u);
            if(sz[v]%2==0)ans++;
            sz[u]+=sz[v];
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    int n;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX