【题解】[SDOI2021 Day5]平凡 题解

前言

给出一种线性(不算建虚树)的不用换根的做法 by ds,代码好写但是推导和证明有一定难度。

思路

定义 $S_v=$ 以 $v$ 为一条路线端点的合法方案数,则:

ans=14∑vSvans=\frac{1}{4}\sum_{v}S_v
ask(x)=ans−Sxask(x)=ans-S_x

定义 $g(v,u)=$ 与路径 $v\to u$ 不相交的路径数量,则:

Sv=∑u≠v,cu=cvg(v,u)S_v=\sum\limits_{u\neq v,c_u=c_v} g(v,u)

定义:

  • $W_v=$ 完全不经过点 $v$ 的路径数量。
  • $E_v=$ 完全不使用边 $(v,fa(v))$ 的路线数。

对于一条路线 $P=v\to u$,有:

g(v,u)=∑x∈PWx−∑e∈PEeg(v,u)=\sum_{x\in P} W_x – \sum_{e\in P} E_e

对 $W,E$ 使用树上前缀和,再加上 LCA 就可以 $O(1)/O(\log)$ 求 $g(v,u)$,问题转化为求 $W,E$。


记 $s_{v,c}$ 表示子树 $v$ 内颜色为 $c$ 的点的个数。

  1. 完全在子树 $v$ 内的路线:$w_I[v]=\sum_{c}\binom{s_{v,c}}{2}$,可以用虚树求(见下文)
  2. 恰好一个端点在子树 $v$ 内的路线:
wsum[v]=∑x∈sub(v)cntcx cross(v)=wsum[v]−szv−2wI[v]wsum[v]=\sum_{x\in sub(v)}cnt_{c_x}\ cross(v)=wsum[v]-sz_v-2w_I[v]
  1. 两端都在子树外的路线:
R=∑c(cntc2) wO[v]=R−wI[v]−cross(v)R=\sum_{c}\binom{cnt_c}{2}\ w_O[v]=R-w_I[v]-cross(v)
  1. 所以:
W[v]=wO[v]+∑y∈son(v)wI[y] E[v]=wI[v]+wO[v]W[v]=w_O[v]+\sum_{y\in son(v)}w_I[y]\ E[v]=w_I[v]+w_O[v]

现在只需要计算 $S_v$。

记 $pW,pE$ 为 $W,E$ 的树上前缀和数组(从根到 $v$ 的和),$l=lca(v,u)$,则:

g(v,u)=(pWv+pWu−2pWl+Wl)−(pEv+pEu−2pEl)g(v,u)=(pW_v+pW_u-2pW_l+W_l)-(pE_v+pE_u-2pE_l)

记 $A_x=pW_x-pE_x,h_x=W_x-2A_x$,则:

g(v,u)=Av+Au+hlg(v,u)=A_v+A_u+h_l

于是对于一种颜色 $C$,对于 $v\in C$ 有:

Sv=∑u∈C,u≠vg(v,u)=(cntc−1)Av+∑u∈C,u≠vAu+∑u≠vhlca(v,u)S_v=\sum_{u\in C,u\neq v}g(v,u)=(cnt_c-1)A_v+\sum_{u\in C,u\neq v}A_u+\sum_{u\neq v}h_{lca(v,u)}

令 $T_v=\sum_{u\in C,u\neq v}h_{lca(v,u)}$,则:

Sv=(cntc−2)Av+∑u∈CAu+TvS_v=(cnt_c-2)A_v+\sum_{u\in C}A_u+T_v

前两项都好求,现在只需要求 $T_v$。

对于颜色 $C$ 和点 $v\in C$,记

qv=#{u∈C:u∈sub(v)},qroot=cntcq_v=\#\{u\in C:u\in sub(v)\}, q_{root}=cnt_c

记点 $v$ 到根的路径为 $r_0=root,r_1,\dots,r_d=v$,则有:

∑u∈Chlca(v,u)=∑j=0dhrj(qrj−qrj+1)\sum_{u\in C}h_{lca(v,u)}=\sum_{j=0}^{d}h_{r_j}(q_{r_j}-q_{r_{j+1}})

(令 $q_{r_{d+1}}=0$)

然后做一些推式子,类似将 $q$ 主元:

∑u∈Chlca(v,u)=qr0hr0−hrdqrd+1+∑j=1dqrj(hrj−hrj−1)=cntc⋅hroot+∑x∈root→v,x≠rootqxΔhxΔhx=hx−hfa(x)\begin{array}{} \sum_{u\in C}h_{lca(v,u)}=q_{r_0}h_{r_0}-h_{r_d}q_{r_{d+1}}+\sum_{j=1}^d q_{r_j}(h_{r_j}-h_{r_{j-1}})\\ = cnt_c\cdot h_{root}+\sum_{x\in root\to v,x\neq root}q_x \Delta h_x\\ \Delta h_x=h_x-h_{fa(x)} \end{array}

所以:

Tv=psv−hvpsv:=∑x∈root→vqxΔhx\begin{array}{} T_v=ps_v-h_v\\ ps_v:= \sum_{x\in root\to v} q_x\Delta h_x \end{array}

$ps$ 可以用树上前缀和求,直接在原树上求就是 $O(nk)$ 的,但可以把这个放到虚树上推。


代码

虚树可以复用,而且不用显式的建出来,直接按 dfn 序到序遍历即可。然后各种地方都可以用 dfn 序正序或倒序遍历,就不用写 dfs 了。

我写了个 $O(1)$ LCA,所以代码的复杂度瓶颈在建虚树的排序和二分,需要 $O(n\log n)$,其余的就按着式子写,都是线性的。

C++
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x":"<<(x)<<' '
#define dbe(x) cerr<<#x":"<<(x)<<'\n'
#define eb emplace_back
#define ep emplace
#define endl '\n'
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
int main(){
    // freopen("route.in","r",stdin);
    // freopen("route.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k;
    cin>>n>>m>>k;
    vi c(n+1);
    for(int i=1;i<=n;i++)cin>>c[i];
    vector<vi>G(n+1);
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].eb(v),G[v].eb(u);
    }
    vi dfn(n+1),dep(n+1),fa(n+1),ds(n+1),fst(n+1),lg;// ds 为 dfn 序列
    const int KMX=18;
    vector<vi>st(KMX+1);/*erase fa*/{
        vi eu;eu.reserve(n*2);
        int dfncnt=0;
        auto dfs=[&](int u,int f,auto&&dfs)->void {
            if(f)G[u].erase(find(G[u].begin(),G[u].end(),f));
            dfn[u]=++dfncnt,dep[u]=dep[f]+1,fa[u]=f,ds[dfncnt]=u;
            fst[u]=eu.size(),eu.eb(u);
            for(int v:G[u])dfs(v,u,dfs),eu.eb(u);
        };dfs(1,0,dfs);
        int m=eu.size();
        for(vi&v:st)v.resize(m);
        for(int i=0;i<m;i++)st[0][i]=eu[i];
        for(int k=1;k<=KMX;k++){
            for(int i=0;i+(1<<k)-1<m;i++){
                int a=st[k-1][i],b=st[k-1][i+(1<<(k-1))];
                st[k][i]=(dep[a]<dep[b]?a:b);
            }
        }
        lg.resize(m+1);
        for(int i=2;i<=m;i++)lg[i]=lg[i/2]+1;
    }
    auto LCA=[&](int u,int v){// O(1) LCA
        int a=fst[u],b=fst[v];if(a>b)swap(a,b);
        int k=lg[b-a+1];
        int x=st[k][a],y=st[k][b-(1<<k)+1];
        return dep[x]<dep[y]?x:y;
    };
    vector<vi>V(k+1),Pv(k+1);vi cnt(k+1);{//build v-tree; V: v-tree, sort by dfn; Pv: v-tree father
        for(int i=1;i<=n;i++)V[c[ds[i]]].eb(ds[i]);// 按 dfn 序加入节点,可以省去一次 sort
        for(int i=1;i<=k;i++)cnt[i]=V[i].size();
        for(int i=1;i<=k;i++){// 两遍 sort 建虚树
            int m=V[i].size();
            if(m<2)continue;
            vi&p=V[i];
            for(int j=1;j<m;j++)p.eb(LCA(p[j-1],p[j]));
            sort(p.begin(),p.end(),[&](int x,int y){return dfn[x]<dfn[y];});
            p.resize(unique(p.begin(),p.end())-p.begin());
            m=p.size();Pv[i].resize(m);
            for(int j=0;j+1<m;j++){
                int lca=LCA(p[j],p[j+1]);
                Pv[i][j+1]=lower_bound(p.begin(),p.end(),lca,[&](int x,int y){
                    return dfn[x]<dfn[y];
                })-p.begin();
            }
        }
    }
    vl W(n+1),E(n+1);{
        vl wI(n+1);{
            for(int i=1;i<=k;i++){
                int m=V[i].size();
                if(m<2)continue;
                vi sz(m);vl cnt(m);
                for(int j=m-1;j>=0;j--){
                    int u=V[i][j];
                    sz[j]+=(c[u]==i),cnt[j]+=ll(sz[j]-1)*sz[j]/2;
                    wI[u]+=cnt[j];
                    if(j)sz[Pv[i][j]]+=sz[j],cnt[Pv[i][j]]-=ll(sz[j]-1)*sz[j]/2;
                }
            }
            for(int i=n;i>=1;i--)for(int v:G[ds[i]])wI[ds[i]]+=wI[v];
        }
        vi sz(n+1,1);for(int i=n;i>=1;i--)sz[fa[ds[i]]]+=sz[ds[i]];
        vl wsum(n+1);for(int i=n;i>=1;i--)wsum[fa[ds[i]]]+=(wsum[ds[i]]+=cnt[c[ds[i]]]);
        vl cross(n+1);for(int i=1;i<=n;i++)cross[i]=wsum[i]-sz[i]-2*wI[i];
        ll R=0;for(int i=1;i<=k;i++)R+=ll(cnt[i]-1)*cnt[i]/2;
        vl wO(n+1);for(int i=1;i<=n;i++)wO[i]=R-wI[i]-cross[i];
        W=wO;for(int i=n;i>=1;i--)W[fa[ds[i]]]+=wI[ds[i]];
        for(int i=1;i<=n;i++)E[i]=wI[i]+wO[i];
    }
    vl pW=W,pE=E;{
        for(int i=1;i<=n;i++){
            int u=ds[i];
            pW[u]+=pW[fa[u]],pE[u]+=pE[fa[u]];
        }
    }
    vl S(n+1);{
        vl A(n+1),h(n+1),sumA(n+1);
        for(int i=1;i<=n;i++)A[i]=pW[i]-pE[i],h[i]=W[i]-2*A[i],sumA[c[i]]+=A[i];
        vi q(n+1);vl ps(n+1);
        for(int i=1;i<=k;i++){
            int m=V[i].size();
            if(m<2)continue;
            ll C=cnt[i];
            for(int j=0;j<m;j++)q[V[i][j]]=(c[V[i][j]]==i);
            for(int j=m-1;j>0;j--)q[V[i][Pv[i][j]]]+=q[V[i][j]];
            ps[V[i][0]]=C*h[V[i][0]];
            for(int j=1;j<m;j++){
                int y=V[i][j],z=V[i][Pv[i][j]];
                ps[y]=ps[z]+(ll)q[y]*(h[y]-h[z]);
            }
            for(int j=0;j<m;j++){
                int v=V[i][j];
                if(c[v]==i)S[v]=(C-2)*A[v]+sumA[i]+ps[v]-h[v];
            }
        }
    }
    ll ans;{
        __int128 sum=0;//sum S > LONG_LONG_MAX
        for(int i=1;i<=n;i++)sum+=S[i];
        ans=sum/4;
    }
    cout<<ans<<endl;
    while(m--){
        int x;cin>>x;
        cout<<ans-S[x]<<endl;
    }

    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇