学步园

题目大意：给定一棵树，每个节点有一个颜色，多次求两个节点的路径上有多少种不同的颜色 其中还有两个参数a和b，若苹果树上同时有这两种颜色，ans--

传说中的树上莫队……颜色数既不满足区间加法也不满足区间减法，直接维护极其困难，这种东西就直接考虑莫队好了

但是怎么转移是个问题

首先树分块 然后以左端点所在块为第一键值，右端点在DFS序中的位置为第二键值排序 (优化：若左端点在DFS序中的位置大于右端点的位置，则交换左右端点)

对于每个点我们记录一个状态，表示当前是否加入答案中统计

初始两个端点指向同一位置，状态全为空。然后对于每个询问我们做如下处理

设当前左右端点为x,y，当前询问的左右端点为qx,qy

将x到qx路径上除LCA(x,qx)之外的点状态反转

将y到qy路径上除LCA(y,qy)之外的点状态反转

将LCA(qx,qy)状态反转

统计当前询问的答案

将LCA(qx,qy)状态反转

保证每次询问后，加入答案的点集为(qx,qy)路径上除LCA(qx,qy)之外的点

证明详见VFleaKing的博客 http://vfleaking.blog.163.com/blog/static/174807634201311011201627/

记住如果TLE不一定是常数大或者死循环 可能是莫队写挂了

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 50500
using namespace std;
namespace IOStream{
    const int L=1<<15;
    char buffer[L];
    char *S,*T;
    char Get_Char()
    {
        if(S==T)
        {
            T=(S=buffer)+fread(buffer,1,L,stdin);
            if(S==T)
                return EOF;
        }
        return *S++;
    }
    int Get_Int()
    {
        int re=0;
        char c;
        do c=Get_Char(); while(c<'0'||c>'9');
        while(c>='0'&&c<='9')
            re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
        return re;
    }
}
struct query{
    int x,y,a,b,pos;
    bool operator < (const query &Y) const;
}q[M<<1];
struct abcd{
    int to,next;
}table[M<<1];
int head[M],tot;
int n,m,block,root;
int a[M],belong[M],pos[M],size[M],dpt[M],fa[M][20];
int cnt[M],now,ans[M<<1],l,r;
bool v[M];
bool query :: operator < (const query &Y) const
{
    if(belong[x]==belong[Y.x])
        return ::pos[y] < ::pos[Y.y];
    return belong[x]<belong[Y.x];
}
inline void Add(int x,int y)
{
    table[++tot].to=y;
    table[tot].next=head[x];
    head[x]=tot;
}
void DFS(int x,int from)
{
    static int T=0;
    static int cnt=0;
    int i;
    pos[x]=++T;fa[x][0]=from;
    if(size[belong[from]]==block)
        belong[x]=++cnt;
    else
        belong[x]=belong[from];
    size[belong[x]]++;dpt[x]=dpt[from]+1;
    for(i=head[x];i;i=table[i].next)
        if(table[i].to!=from)
            DFS(table[i].to,x);
}
inline void Change(int x,bool flag)
{
    if(flag)
    {
        cnt[x]++;
        if(cnt[x]==1)
            ++now;
    }
    else
    {
        cnt[x]--;
        if(!cnt[x])
            --now;
    }
}
inline int LCA(int x,int y)
{
    int j;
    if(dpt[x]<dpt[y])
        swap(x,y);
    for(j=15;~j;j--)
        if(dpt[fa[x][j]]>=dpt[y])
            x=fa[x][j];
    if(x==y)
        return x;
    for(j=15;~j;j--)
        if(fa[x][j]!=fa[y][j])
            x=fa[x][j],y=fa[y][j];
    return fa[x][0];
}
int main()
{
    int i,j,x,y,lca;
    cin>>n>>m;
    block=static_cast<int>(sqrt(n+1)+1e-7);
    for(i=1;i<=n;i++)
        a[i]=IOStream::Get_Int();
    for(i=1;i<=n;i++)
    {
        x=IOStream::Get_Int();
        y=IOStream::Get_Int();
        if(!x||!y) root=x+y;
        else Add(x,y),Add(y,x);
    }
    DFS(root,0);
    for(j=1;j<=15;j++)
        for(i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    for(i=1;i<=m;i++)
    {
        x=IOStream::Get_Int();
        y=IOStream::Get_Int();
        if(pos[x]>pos[y]) swap(x,y);
        q[i].x=x;
        q[i].y=y;
        q[i].pos=i;
        q[i].a=IOStream::Get_Int();
        q[i].b=IOStream::Get_Int();
    }
    sort(q+1,q+m+1);
    l=r=root;
    for(i=1;i<=m;i++)
    {
 
        lca=LCA(l,q[i].x);
        for(j=l;j!=lca;j=fa[j][0])
            Change(a[j],v[j]^=1);
        for(j=q[i].x;j!=lca;j=fa[j][0])
            Change(a[j],v[j]^=1);
         
        lca=LCA(r,q[i].y);
        for(j=r;j!=lca;j=fa[j][0])
            Change(a[j],v[j]^=1);
        for(j=q[i].y;j!=lca;j=fa[j][0])
            Change(a[j],v[j]^=1);
 
        l=q[i].x;r=q[i].y;
        lca=LCA(l,r);
        Change(a[lca],v[lca]^=1);
 
        ans[q[i].pos]=now;
        if( q[i].a!=q[i].b && cnt[q[i].a] && cnt[q[i].b] )
            ans[q[i].pos]--;
 
        Change(a[lca],v[lca]^=1);
 
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}