显然容斥后转化为求树链的交。这个题非常良心的保证了查询的路径都是到祖先的，求交就很休闲了。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 200010#define ui unsigned int#define inf ((ui)4294967295)#define p31 2147483647char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,p[N],fa[N],deep[N],son[N],size[N],top[N],dfn[N],L[N<<2],R[N<<2],u[6],v[6],flag[6],k,cnt,t;ui tree[N<<2],lazy[N<<2],ans;struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs1(int k){ size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { fa[edge[i].to]=k; deep[edge[i].to]=deep[k]+1; dfs1(edge[i].to); size[k]+=size[edge[i].to]; if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to; }}void dfs2(int k,int from) { dfn[k]=++cnt;top[k]=from; if (son[k]) dfs2(son[k],from); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs2(edge[i].to,edge[i].to);}void build(int k,int l,int r){ L[k]=l,R[k]=r; if (l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);}void up(int k){tree[k]=tree[k<<1]+tree[k<<1|1];}void update(int k,ui x){tree[k]+=(R[k]-L[k]+1)*x,lazy[k]+=x;}void down(int k){update(k<<1,lazy[k]),update(k<<1|1,lazy[k]),lazy[k]=0;}void add(int k,int l,int r,ui x){ if (L[k]==l&&R[k]==r){update(k,x);return;} if (lazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) add(k<<1,l,r,x); else if (l>mid) add(k<<1|1,l,r,x); else add(k<<1,l,mid,x),add(k<<1|1,mid+1,r,x); up(k);}ui query(int k,int l,int r){ if (L[k]==l&&R[k]==r) return tree[k]; if (lazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);}ui sum(int x,int y){ ui ans=0; while (top[x]!=top[y]) { if (deep[top[x]]
           
            =dfn[y];}void calc(int op){ int x=0,y=0; for (int i=1;i<=k;i++) if (flag[i]) { if (!x) x=u[i],y=v[i]; else { int p=u[i],q=v[i]; if (deep[x]>deep[p]) swap(x,p),swap(y,q); if (in(x,p)&&in(p,y)) x=p,y=lca(y,q); else return; } } if (x==0) return; else if (op>0) ans+=sum(x,y); else ans+=inf-sum(x,y)+1;}void dfs(int cur,int op){ if (cur>k) {calc(op);return;} flag[cur]=1;dfs(cur+1,-op); flag[cur]=0;dfs(cur+1,op);}int main(){#ifndef ONLINE_JUDGE freopen("bzoj3589.in","r",stdin); freopen("bzoj3589.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i
            
             dfn[v[i]]) swap(u[i],v[i]); dfs(1,-1);printf("%u\n",ans&p31); } } return 0;}