【题目大意】

给定一个有n(n<=500000)个点，m(1<=500000)条边的无向图。给Q(1<=500000)个询问ui和vi，问ui和vi之间是否存在一条不经过重复点的路径，使得经过的点数为偶数。

【题目解析】

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define re(i,a,b) for(i=(a);i<=(b);i++)#define red(i,a,b) for(i=(a);i>=(b);i--)#define SF scanf#define PF printf#define mmst(a,v) memset(a,v,sizeof(a))int gint()  {        int res=0;bool neg=0;char z;        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());        if(z==EOF)return 0;        if(z=='-'){neg=1;z=getchar();}        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());        return (neg)?-res:res;     }const int maxn=500000;int n,m,Q;int now,info[maxn+100];struct Tedge{
    int v,next;}edge[2*maxn+100];int treeedge[2*maxn+100];void addedge(int u,int v){now++;edge[now].v=v;edge[now].next=info[u];info[u]=now;}int dep[maxn+100],jump[maxn+100][31];int odd[maxn+100],f[maxn+100];void dfs(int u)  {      int i,j,v;      for(i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)        if(!dep[v])          {              dep[v]=dep[u]+1;              jump[v][0]=u;              re(j,1,25)jump[v][j]=jump[jump[v][j-1]][j-1];              treeedge[i]=treeedge[i^1]=1;              dfs(v);              odd[u]+=odd[v];          }        else          if(!treeedge[i] && dep[u]>dep[v] && (dep[u]-dep[v])%2==0)            {                odd[u]++;                odd[v]--;            }  }void dfs2(int u)  {      int i,v;      f[u]=f[jump[u][0]]+odd[u];      for(i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)if(treeedge[i] && dep[v]>dep[u])dfs2(v);  }void swim(int &x,int H){
    int i;for(i=0;H!=0;H>>=1,i++)if(H&1)x=jump[x][i];}int ask_lca(int x,int y)  {      if(dep[x]
          
           =1 || f[y]-f[lca]>=1)PF("TAK\n");else PF("NIE\n");            }        return 0;    }