题解：P14260 期待（counting）

· · 题解

tag：树形结构，计数。

以下为了表述方便，称期待的方案为合法。

暴力

直接枚举所有合法移动方案，复杂度 O(n^3)，期望得分 15+?。

特殊性质 B

祖传不按顺序讲特殊性质。

菊花图部分分。

事实上发现在菊花图上只有四种本质不同的情况，直接求出对应答案公式即可。

若 y\neq s，则有两种情况：

复杂度 O(n)，期望得分 20。

特殊性质 C

链部分分。不妨设 i 与 i+1 连边，我们可以自然地定义从小到大和从大到小两种移动方向。

首先考虑合法移动方案的条件。样例非常良心地给我们提示了一种小 corner case：在一条边上两端点互换。容易发现只有这一种情况可以使得两棋子移动方向不同。以下不再赘述。

发现其余情况下只要两棋子移动方向相同则方案合法。再根据非常良心的样例解释容易发现除了 (y,s) 不动外的所有方案都可以两两配对，每对恰互为调换移动方向后的结果。因此我们只考虑从小到大的情况。

如上我们将问题转化为：求区间组 [l_1,r_1],[l_2,r_2] 的数量，使得 r_1-l_1+1=r_2-l_2+1，且 l_1\le y\le r_1,l_2\le s\le r_2。

直接枚举 l_1,l_2 可以 O(1) 求出方案数，期望得分 10。

考虑 l=\min\{l_1,l_2\},r=\max\{r_1,r_2\}，显然 l\le y,s\le r。若 l_1=l,r_2=r，则要求 r_1\ge y,l_2\le s，有 \min\{r-y+1,s-l+1\} 种可能。同理 l_2=l,r_1=r 有 \min\{r-s+1,y-l+1\} 种可能。其中有一种重复方案：l_1=l_2,r_1=r_2。

不妨设 y\le s，由上可知 l=y-i,r=s+j 时有 (s-y)+2\min\{i,j\}+1 种方案，即求 \sum_{i=0}^{y-1}\sum_{j=0}^{n-s}\left((s-y)+2\min\{i,j\}+1\right)，容易后缀和优化 O(n) 求出。期望得分 20。

特殊性质 A

完全二叉树的大部分性质我不知道怎么用。这个部分分是正解的一部分。

容易证明合法移动方案中经过的所有点一定在同一条链上。只要确定这条链就可以沿用链部分分的解法。

考虑以 s 为根时 y 的子树中点作为 l，以 y 为根时 s 的子树中点作为 r，类似地只需求 \sum_l\sum_r(dis(s,y)+2\min\{dis(y,l)+dis(s,r)\}+1)，因为 dis(y,l) 和 dis(s,r) 都是 O(\log n) 的，统计深度相同的点数后直接计算可以做到 O(\log^2n)。

正解

同完全二叉树部分分直接算可以做到 O(n^2)。同链部分分可以优化至 O(n)，期望得分 100。

Code:

int n,y,s;
int d[100003];
vector<int>e[100003];

int c0[100003];
int c1[100003];
int dep[100003],dp0,dp1;
void dfs(int u,int fa){
    for(int i=0,v;i<d[u];++i){
        v=e[u][i];if(v==fa)continue;
        dep[v]=dep[u]+1;dp0=max(dp0,dep[v]);
        ++c0[dep[v]];dfs(v,u);
    }
}

int dis;
void dfs1(int u,int fa){
    if(u==s){
        dis=dep[u];
        dep[u]=dp0=0;
        c0[0]=1;dfs(u,fa);
        return;
    }for(int i=0,v;i<d[u];++i){
        v=e[u][i];if(v==fa)continue;
        dep[v]=dep[u]+1;dfs1(v,u);
    }
}

ll ans;
inline void solve(){
    cin>>n>>y>>s;ans=0;
    for(int i=1;i<=n;++i){
        d[i]=0;e[i].clear();
    }for(int i=1,u,v;i<n;++i){
        cin>>u>>v;++d[u],++d[v];
        e[u].push_back(v);
        e[v].push_back(u);
    }dep[y]=0;dfs1(y,0);
    for(int i=0;i<=dp0;++i)
        c1[i]=c0[i],c0[i]=0;
    dp1=dp0;swap(y,s);
    dep[y]=0;dfs1(y,0);
    for(int i=max(dp0,dp1);i>=0;--i)
        ans+=((ll)c0[i]*c1[i+1]+(ll)c1[i]*c0[i+1]+(ll)c0[i]*c1[i])*(dis+i*2+1),\
        c0[i]+=c0[i+1],c1[i]+=c1[i+1];
    ans=ans*2-1;if(dis==1)ans+=2;
    for(int i=0;i<=n;++i)c0[i]=c1[i]=0;
    cout<<ans<<"\n";
}