CF852I Dating

Harekaze · 2026-08-09 21:36:56 · 题解

树上莫队板子。

直接快进到指针移动，开一个数组 cnt_{0/1,i} 表示男或女中各自喜欢数字 i 的人数，不难发现 i 的贡献是 cnt_{0,i}\times cnt_{1,i}。当 cnt_{c,i}\to cnt_{c,i}\pm 1，答案 ans\pm cnt_{c\oplus 1,i}。

然后那上面的那个东西扔进树上莫队里做到 O(n\sqrt n)。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
struct edge{ll u,v,nxt;}e[2*N];
ll idx,h[N],ans[N],dep[N],vis[N],cnt[2][N],p[N][21];
ll n,q,pos,sum,maxn,b[N],c[N],in[N],out[N],dfn[N<<1];
inline void add(ll u,ll v){e[++idx]={u,v,h[u]},h[u]=idx;}
struct node
{
    ll l,r,f,id;
    friend bool operator<(node a,node b)
    {
        if(a.l/maxn!=b.l/maxn)return a.l<b.l;
        else return (a.l/maxn)&1?a.r<b.r:a.r>b.r;
    }
}a[N];
void dfs(ll u,ll fa)
{
    p[u][0]=fa,dep[u]=dep[fa]+1;
    pos=pos+1,in[u]=pos,dfn[pos]=u;
    for(ll i=1;i<=__lg(dep[u]);i++)p[u][i]=p[p[u][i-1]][i-1];
    for(ll i=h[u];i!=-1;i=e[i].nxt)
    {
        ll v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
    }
    pos=pos+1,out[u]=pos,dfn[pos]=u;
}
ll lca(ll u,ll v)
{
    if(dep[u]<dep[v])swap(u,v);
    for(ll i=__lg(n);i>=0;i--)if(dep[p[u][i]]>=dep[v])u=p[u][i];
    if(u==v)return u;
    for(ll i=__lg(n);i>=0;i--)if(p[u][i]!=p[v][i])u=p[u][i],v=p[v][i];
    return p[u][0];
}
inline void add(array<ll,2>x){sum+=cnt[x[0]^1][x[1]],cnt[x[0]][x[1]]++;}
inline void del(array<ll,2>x){sum-=cnt[x[0]^1][x[1]],cnt[x[0]][x[1]]--;}
inline void tol(ll x){vis[x]?del({b[x],c[x]}):add({b[x],c[x]}),vis[x]^=1;}
int main()
{
    vector<ll>Q;
    scanf("%lld",&n);
    memset(h,-1,sizeof(h)),maxn=sqrt(n);
    for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);
    for(ll i=1;i<=n;i++)scanf("%lld",&c[i]),Q.emplace_back(c[i]);
    sort(begin(Q),end(Q)),Q.erase(unique(begin(Q),end(Q)),end(Q));
    for(ll i=1;i<=n;i++)c[i]=lower_bound(begin(Q),end(Q),c[i])-begin(Q)+1;
    for(ll i=1;i<n;i++)
    {
        ll a,b;
        scanf("%lld%lld",&a,&b);
        add(a,b),add(b,a);
    }
    dfs(1,0),scanf("%lld",&q);
    for(ll i=1;i<=q;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if(in[x]>in[y])swap(x,y);
        ll l,r,f,w=lca(x,y);
        if(w==x)l=in[x],r=in[y],f=-1;
        else l=out[x],r=in[y],f=w;
        a[i]={l,r,f,i};
    }
    sort(a+1,a+1+q);
    ll l=1,r=0;
    for(ll i=1;i<=q;i++)
    {
        while(l>a[i].l)tol(dfn[--l]);
        while(r<a[i].r)tol(dfn[++r]);
        while(l<a[i].l)tol(dfn[l++]);
        while(r>a[i].r)tol(dfn[r--]);
        if(a[i].f!=-1)tol(a[i].f);
        ans[a[i].id]=sum;
        if(a[i].f!=-1)tol(a[i].f);
    }
    for(ll i=1;i<=q;i++)printf("%lld\n",ans[i]);
    return 0;
} 

::::