题解 CF1540B

· · 题解

前言

不可发送单个标点符号。

思路

不难想到对每个最开始选的点分开考虑。

在选定第一个数后，我们考虑每对数的贡献。

不难发现如果令 x 为根，每对数有以下几种情况：

  1. 祖先关系

先取的数已经固定了，贡献只能为 1 或 0。

  1. 非祖先关系。

不难发现在插入它们的 LCA 后，剩下的插入要么与这两个点无关，要么等概率让它们其中的一个距离已选区域距离减 1。

于是，我们可以预处理，插入 LCA 后，两个点需要 x,y 步，第一个点先到的概率。这个预处理十分简单，显然有 f(x,y)=\frac{1}{2}(f(x-1,y)+f(x,y-1))，x=0 时答案为 1，y=0 时答案为 0。

时间复杂度 O(n^3) 或 O(n^3\log n)，代码很好写。

代码

// Problem: CF1540B Tree Array
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1540B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//And in that light,I find deliverance.
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=1e9+7;
int qp(int x,int y)
{
    int res=1;
    for(int t=x; y; y>>=1,t=t*t%p) if(y&1) res=res*t%p;
    return res;
}
int n=read();
vector<int> e[1003];
int s;
int sz[1003];
int f[1003][1003];
//x steps,y steps,x first
void init(int n)
{
    for(int i=1; i<=n; ++i) f[0][i]=1;
    for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
    f[i][j]=(f[i-1][j]+f[i][j-1])*qp(2,p-2)%p;
    return ;
}
void getd(int x,int fa,int v)
{
    if(x<v) ++s;
    for(int i:e[x]) if(i!=fa) getd(i,x,v);
}
void dfs(int x,int fa)
{
    getd(x,fa,x);
    for(int i:e[x]) if(i!=fa) dfs(i,x);
}
vector<pair<int,int> > c[1003];
void calc(int x,int fa,int id,int d)
{
    for(pair<int,int> i:c[id]) if(x>i.first)
        s=(s+f[d][i.second])%p;
    else s=(s+f[i.second][d])%p;
    for(int i:e[x]) if(i!=fa) calc(i,x,id,d+1);
}
void add(int x,int fa,int id,int d)
{
    c[id].push_back(make_pair(x,d));
    for(int i:e[x]) if(i!=fa) add(i,x,id,d+1);
}
void dfs2(int x,int fa)
{
    for(int i:e[x]) if(i!=fa) calc(i,x,x,1),add(i,x,x,1);
    for(int i:e[x]) if(i!=fa) dfs2(i,x);
}
void calc(int x)
{
    for(int i=1; i<=n; ++i) c[i].clear();
    dfs(x,x);
    dfs2(x,x);
}
signed main()
{
    init(n);
    for(int i=1,p,q; i<n; ++i) 
    p=read(),q=read(),e[p].push_back(q),e[q].push_back(p); 
    for(int i=1; i<=n; ++i)
    calc(i);
    printf("%lld\n",s*qp(n,p-2)%p);
    return 0;
}