SPOJ COT2 - Count on a tree II

SPOJ

Luogu

分析

树上莫队板子题...?

首先把树的欧拉序爬下来。设 $st_u$ 表示第一个 $u$ 的位置,$ed_u$ 表示最后一个 $u$ 的位置。

考虑一个询问 $(u,v)$ 怎么统计。为了方便,设 $st_u<st_v$ 。

  • 如果 $lca(u,v)=u$ ,那么 $(u,v)$ 路径上的点就是欧拉序的 $[st_u,st_v]$ 中只出现过一次的点,莫队统计即可。
  • 如果 $lca(u,v)\neq u$ ,那么 $(u,v)$ 路径上的点就是欧拉序的 $[ed_u,st_v]$ 中只出现过一次的点加上 $lca$ ,同样莫队统计即可。

具体莫队统计的方式很简单,开一个桶维护一下每种颜色的数量,然后再维护一个标记判断当前点应该是删除还是添加即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=40000+10,M=100000+10;

int n,m,w[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],fa[N],sz[N],hson[N],top[N];
int st[N],ed[N],seq[N<<1],tim=0;
inline void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    st[u]=++tim,seq[tim]=u; top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
    ed[u]=++tim,seq[tim]=u;
}
inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

int bl[N<<1],block,Ans[M],o[N],mark[N],ans=0;
struct query { int l,r,lca,id; } q[M];
bool operator <(query a,query b) {
    return bl[a.l]!=bl[b.l]?a.l<b.l:((bl[a.l]&1)?a.r<b.r:a.r>b.r);
}
inline void add(int x) { if (!o[x]) ++ans; ++o[x]; }
inline void del(int x) { --o[x]; if (!o[x]) --ans; }
inline void work(int x) {
    mark[x]?del(w[x]):add(w[x]); mark[x]^=1;
}
inline void solve() {
    block=sqrt(n<<1);
    for (re int i=1;i<=n<<1;++i) bl[i]=i/block+1;
    sort(q+1,q+m+1);
    for (re int i=1,l=1,r=0;i<=m;++i) {
        while (l<q[i].l) work(seq[l]),++l;
        while (l>q[i].l) --l,work(seq[l]);
        while (r<q[i].r) ++r,work(seq[r]);
        while (r>q[i].r) work(seq[r]),--r;
        if (q[i].lca) work(q[i].lca);
        Ans[q[i].id]=ans;
        if (q[i].lca) work(q[i].lca);
    }
}

int S[N];
int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) S[i]=w[i]=read();
    sort(S+1,S+n+1); int tp=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) w[i]=lower_bound(S+1,S+tp+1,w[i])-S;
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),t=getlca(u,v);
        if (st[u]>st[v]) swap(u,v);
        if (t==u) q[i]=(query){st[u],st[v],0,i};
        else q[i]=(query){ed[u],st[v],t,i};
    }
    solve();
    for (re int i=1;i<=m;++i) printf("%d\n",Ans[i]);
    return 0;
}
最后修改:2019 年 10 月 04 日 04 : 19 PM

发表评论