AC日记——Count on a tree II spoj

╰+哭是因爲堅強的太久メ 2021-09-29 04:28 176阅读 0赞

[Count on a tree II][]

思路：

树上莫队；

先分块，然后，就好办了；

来，上代码：

#include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    #define maxn 40005
    #define maxm 100005
    
    struct QueryType {
        int u,v,id;
    };
    struct QueryType qu[maxm];
    
    int n,m,ti[maxn],num[maxn],Hash[maxn],siz;
    int bel[maxn],f[maxn],deep[maxn],ans[maxm];
    int E[maxn<<1],V[maxn<<1],head[maxn],cnt=0;
    int top[maxn],size[maxn],dis[maxn],sizee;
    
    bool if_[maxn];
    
    inline void in(int &now)
    {
        char Cget=getchar();now=0;
        while(Cget>'9'||Cget<'0') Cget=getchar();
        while(Cget>='0'&&Cget<='9')
        {
            now=now*10+Cget-'0';
            Cget=getchar();
        }
    }
    
    void pre(int now,int fa)
    {
        f[now]=fa,deep[now]=deep[fa]+1;
        bel[now]=(++cnt+1)/siz,size[now]=1;
        for(int i=head[now];i;i=E[i])
        {
            if(V[i]==fa) continue;
            pre(V[i],now),size[now]+=size[V[i]];
        }
    }
    
    void dfs(int now,int chain)
    {
        top[now]=chain;int pos=0;
        for(int i=head[now];i;i=E[i])
        {
            if(V[i]==f[now]) continue;
            if(size[V[i]]>size[pos]) pos=V[i];
        }
        if(pos==0) return ;
        dfs(pos,chain);
        for(int i=head[now];i;i=E[i])
        {
            if(V[i]==f[now]||V[i]==pos) continue;
            dfs(V[i],V[i]);
        }
    }
    
    int solve_lca(int x,int y)
    {
        while(top[x]!=top[y])
        {
            if(deep[top[x]]<deep[top[y]]) swap(x,y);
            x=f[top[x]];
        }
        if(deep[x]>deep[y]) swap(x,y);
        return x;
    }
    
    bool cmp(QueryType aa,QueryType bb)
    {
        if(bel[aa.u]==bel[bb.u]) return bel[aa.v]<bel[bb.v];
        else return bel[aa.u]<bel[bb.u];
    }
    
    inline void updata(int to)
    {
        if(if_[to])
        {
            ti[num[to]]--;
            if(ti[num[to]]==0) cnt--;
        }
        else
        {
            ti[num[to]]++;
            if(ti[num[to]]==1) cnt++;
        }
        if_[to]=!if_[to];
    }
    
    int main()
    {
        in(n),in(m);siz=sqrt(n);
        for(int i=1;i<=n;i++) in(num[i]),Hash[i]=num[i];
        sort(Hash+1,Hash+n+1);
        sizee=unique(Hash+1,Hash+n+1)-Hash-1;int u,v;
        for(int i=1;i<=n;i++) num[i]=lower_bound(Hash+1,Hash+sizee+1,num[i])-Hash;
        for(int i=1;i<n;i++)
        {
            in(u),in(v);
            E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
            E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
        }
        cnt=0,pre(1,0),dfs(1,1);
        for(int i=1;i<=m;i++)
        {
            in(qu[i].u),in(qu[i].v),qu[i].id=i;
            if(bel[qu[i].u]>bel[qu[i].v]) swap(qu[i].u,qu[i].v);
        }
        sort(qu+1,qu+m+1,cmp);u=1,v=1,cnt=0;
        for(int no=1;no<=m;no++)
        {
            int lca=solve_lca(u,qu[no].u);
            while(u!=f[lca]) updata(u),u=f[u];u=qu[no].u;
            while(u!=f[lca]) updata(u),u=f[u];u=qu[no].u;
            lca=solve_lca(v,qu[no].v);
            while(v!=f[lca]) updata(v),v=f[v];v=qu[no].v;
            while(v!=f[lca]) updata(v),v=f[v];v=qu[no].v;
            lca=solve_lca(u,v);
            updata(lca),ans[qu[no].id]=cnt,updata(lca);
        }
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6763482.html

[Count on a tree II]: http://www.spoj.com/problems/COT2/