BZOJ 3757 苹果树

BZOJ

GDOI

首先，看见不同颜色之类的话就要想到莫队，但是这次问题出在了树上，所以是树上莫队?

没错！

普通莫队是在一个一个地移动指针，树上莫队是一个一个爬节点----SXYZ巨佬

图片引自洛谷

首先，假设你知道了欧拉序是什么东西，不知道出门右拐百度。

这棵树的欧拉序就是 $1,2,4,6,6,7,7,5,5,4,2,3,3,1$

有什么性质，仔细观察，每个数都出现了两次，而且左边的那个数和右边的那个数夹着的正好是它的子树。

我们设 $L[u]$ 为 $u$ 第一次出现在欧拉序中它的编号， $R[u]$ 为 $u$ 最后一次出现在欧拉序中它的编号。

如 $L[4]=3,R[4]=10$ 。

树上莫队其实上就是在欧拉序上面爬来爬去。

假设现在我们要查询 $(u,v)$ 这条链，首先我们要调教一下这条链，假设 $L[u]>L[v]$ ，要交换一下 $u,v$ ，这其实就是保证了查询的区间左端点小于右端点。

我们分情况讨论：

1. $LCA(u,v)==u$ ，即 $v \in subtree(u)$

查询的即是 $[L[u],L[v]]$ 这段区间

1	if (u==lca) q[i]=make_q(L[u],L[v],0,i,a,b);//u为这条链的顶点

2. $LCA(u,v)!=u$ ，即 $v \notin subtree(u)$

这种情况查询的就不是 $[L[u],L[v]]$ ，考虑一下刚才说的性质： $[L[u]+1,R[u]-1]$ 之间是 $u$ 的子树，如果你还是按照这样算的话， $u$ 的子树也会统计进去。

于是查询的区间变成 $[R[u],L[v]]$

1	else q[i]=make_q(R[u],L[v],lca,i,a,b);

对了，还有一个细节，发现对于第一种情况 $LCA(u,v)==u$ ，所以 $LCA(u,v)$ 会被统计到，不用管，但是第二种情况就会出锅，于是我们再记录一个 $lca$ 就可以了。

回到本题，如果没有色盲这道题就是裸题，但是加入色盲怎么搞？

考虑分类讨论，假设没有 $a$ 这种颜色，那么什么都不用考虑，如果有 $a$ ，但是没有 $b$ ，就是把 $a$ 替换成 $b$ ，答案不变，于是只用考虑有 $a$ ，也有 $b$ 的情况，答案减1

注意 $a==b$ 的特判。

#include <bits/stdc++.h>
#define MAXN 200005
#define MAXM 17
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int c[MAXN];//每个点的颜色
int anc[MAXN][MAXM],dep[MAXN];
int euler[MAXN];//欧拉序(出栈入栈都要记录)
int L[MAXN],R[MAXN];//左右端点
int tot;
void dfs(int u,int father){
    dep[u]=dep[father]+1;
    anc[u][0]=father;
    euler[L[u]=++tot]=u;
    for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father) dfs(v,u);
    }
    euler[R[u]=++tot]=u;
}
inline int LCA(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]){
            u=anc[u][i],v=anc[v][i];
        }
    }
    return anc[u][0];
}

int n,m;

int b[MAXN];//块编号
struct Query{
    int u,v,lca,id,a,b;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){//莫队的玄学优化
    return (b[A.u]^b[B.u])?b[A.u]<b[B.u]:((b[A.u]&1)?A.v<B.v:A.v>B.v);
}
int inq[MAXN];//在不在莫队维护的范围内
int ans,cnt[MAXN];
inline void Update(int i){//相应地加上/减去元素
    if (!inq[i]){//加上
        cnt[c[i]]++;
        if (cnt[c[i]]==1) ans++;
        inq[i]=true;
    }
    else {
        cnt[c[i]]--;
        if (cnt[c[i]]==0) ans--;
        inq[i]=false;
    }
}
int Ans[MAXN];
inline Query make_q(int u,int v,int lca,int id,int a,int b){
    Query temp;
    temp.id=id;
    temp.u=u,temp.v=v;
    temp.lca=lca;
    temp.a=a,temp.b=b;
    return temp;
}
int main(){
    n=read(),m=read();int Size=sqrt(n);//块大小
    for (register int i=0;i<MAXN;++i){
        b[i]=i/Size+1;
    }
    for (register int i=1;i<=n;++i){
        c[i]=read();
    }
    int rt;
    for (register int i=1;i<=n;++i){
        int u=read(),v=read();
        if (u==0) rt=v;
        if (v==0) rt=u;
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(rt,rt);
    for (register int i=1;i<=m;++i){
        int u=read(),v=read(),a=read(),b=read();
        if (L[u]>L[v]) swap(u,v);//保证这条链是从左往右
        int lca=LCA(u,v);
        if (u==lca) q[i]=make_q(L[u],L[v],0,i,a,b);//u为这条链的顶点
        else q[i]=make_q(R[u],L[v],lca,i,a,b);
    }
    sort(q+1,q+1+m);
    int l=1,r=0;//模仿STL队列
    for (register int i=1;i<=m;++i){
        while (l<q[i].u) Update(euler[l++]);
        while (l>q[i].u) Update(euler[--l]);
        while (r<q[i].v) Update(euler[++r]);
        while (r>q[i].v) Update(euler[r--]);
        if (q[i].lca) Update(q[i].lca);//注意处理lca
        Ans[q[i].id]=ans;
        if (cnt[q[i].a]&&cnt[q[i].b]&&q[i].a!=q[i].b) Ans[q[i].id]--;
        if (q[i].lca) Update(q[i].lca);
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}