【bzoj3757】苹果树

2015.05.01 14:53 Fri | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

神犇家门口种了一棵苹果树。苹果树作为一棵树,当然是呈树状结构,每根树枝连接两个苹果,每个苹果都可以沿着一条由树枝构成的路径连到树根,而且这样的路径只存在一条。由于这棵苹果树是神犇种的,所以苹果都发生了变异,变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码,号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。
有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题,才能进屋膜拜神犇。这个问题就是,从树上编号为u的苹果出发,由树枝走到编号为v的苹果,路径上经过的苹果一共有多少种不同的颜色(包括苹果u和苹果v的颜色)?不过神犇注意到,有些来膜拜的人患有色盲症。具体地说,一个人可能会认为颜色a就是颜色b,那么他们在数苹果的颜色时,如果既出现了颜色a的苹果,又出现了颜色b的苹果,这个人只会算入颜色b,而不会把颜色a算进来。
神犇是一个好人,他不会强人所难,也就会接受由于色盲症导致的答案错误(当然答案在色盲环境下也必须是正确的)。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟,但是他想考验一下你。你能替神犇完成这项任务吗?

Input

输入第一行为两个整数n和m,分别代表树上苹果的个数和前来膜拜的人数。
接下来的一行包含n个数,第i个数代表编号为i的苹果的颜色Coli。
接下来有n行,每行包含两个数x和y,代表有一根树枝连接了苹果x和y(或者根和一个苹果)。
接下来有m行,每行包含四个整数u、v、a和b,代表这个人要数苹果u到苹果v的颜色种数,同时这个人认为颜色a就是颜色b。如果a=b=0,则代表这个人没有患色盲症。

Output

输出一共m行,每行仅包含一个整数,代表这个人应该数出的颜色种数。

Sample Input

5 3
1 1 3 3 2
0 1
1 2
1 3
2 4
3 5
1 4 0 0
1 4 1 3
1 4 1 2

Sample Output

2
1
2

HINT

0<=x,y,a,b<=N
N<=50000
1<=U,V,Coli<=N

题解

树上莫队,不懂的依然请移步vfk博客

我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 50005
int n,q,m,block,cnt,root,pos[N],ans[N*20],c[N];
int vis[N],num[N],now;
int fa[N][17],dep[N],dfn[N],dfn_clock;
int st[N],top;
struct Que
{
    int a,b,l,r,id;
}a[N*20];
struct edge
{
    int to;
    int next;
}e[N*2];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int dfs(int x)
{
    int size=0;
    dfn[x]=++dfn_clock;
    for(int i=1;i<=16;i++)
        if(dep[x]>=(1<<i))
            fa[x][i]=fa[fa[x][i-1]][i-1];
        else break;
    for(int i=h[x];e[i].to;i=e[i].next)
        if(e[i].to!=fa[x][0])
        {
            dep[e[i].to]=dep[x]+1;
            fa[e[i].to][0]=x;
            size+=dfs(e[i].to);
            if(size>=block)
            {
                cnt++;
                for(int k=1;k<=size;k++)
                    pos[st[top--]]=cnt;
                size=0;
            }
        }
    st[++top]=x;
    return size+1;
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    int t=dep[x]-dep[y];
    for(int i=0;(1<<i)<=t;i++)
        if(t&(1<<i)) x=fa[x][i];
    for(int i=16;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(x==y)return x;
    return fa[x][0];
}
bool cmp(const Que &a,const Que &b)
{
    if(pos[a.l]==pos[b.l]) return dfn[a.r]<dfn[b.r];
    return dfn[a.l]<dfn[b.l];
}
void reverse(int x)
{
    if(!vis[x])
    {
        vis[x]=1;num[c[x]]++;
        if(num[c[x]]==1) now++;
    }
    else
    {
        vis[x]=0;num[c[x]]--;
        if(!num[c[x]]) now--;
    }
}
void solve(int u,int v)
{
    while(v!=u)
        if(dep[u]>dep[v]) reverse(u),u=fa[u][0];
        else reverse(v),v=fa[v][0];
}
int main()
{
    n=read();q=read();
    block=int(sqrt(n));
    for(int i=1;i<=n;i++) c[i]=read();
    for(int u,v,i=1;i<=n;i++)
    {
        u=read();v=read();
        if(!u) root=v;
        else if(!v) root=u;
        else ae(u,v),ae(v,u);
    }
    dfs(root);cnt++;
    while(top) pos[st[top--]]=cnt;
    for(int i=1;i<=q;i++)
    {
        a[i].l=read(),a[i].r=read(),a[i].a=read(),a[i].b=read();
        if(dfn[a[i].l]>dfn[a[i].r]) swap(a[i].l,a[i].r);
        a[i].id=i;
    }
    sort(a+1,a+q+1,cmp);
    int t=lca(a[1].l,a[1].r);
    solve(a[1].l,a[1].r);
    reverse(t);
    ans[a[1].id]=now;
    if(num[a[1].a]&&num[a[1].b]&&a[1].a!=a[1].b)ans[a[1].id]--;
    reverse(t);
    for(int i=2;i<=q;i++)
    {
        solve(a[i-1].l,a[i].l);
        solve(a[i-1].r,a[i].r);
        t=lca(a[i].l,a[i].r);
        reverse(t);
        ans[a[i].id]=now;
        if(num[a[i].a]&&num[a[i].b]&&a[i].a!=a[i].b)ans[a[i].id]--;
        reverse(t);
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
}```