“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)题解

D：概率论
条件概率：求在某个条件发生的概率下，另一个条件发生的概率.
公式P(A|B) = P(AB)/P(A).
在这题中即可看成 恰好有k枚的概率/至少m枚的概率.
对于至少m枚的概率.
容斥求最多m-1枚反面的概率.
0枚反面时 C(n,0) * (1/2)^n
1枚反面时 C(n,1) * (1/2)^2
....
1减去这个和即为至少m枚反面的概率.

恰好k枚正面的概率C(n,k)*(1/2)^n.
Code:

LL f[N];
void init()
{
    f[0] = 1;for(int i=1;i<N;++i) f[i] = (f[i-1]*i)%Mod;
}
LL quick_mi(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = (re*a)%Mod;
        a = (a*a)%Mod;
        b >>= 1;
    }
    return re;
}
LL inv(LL n){return quick_mi(n,Mod-2)%Mod;}
LL C(LL n,LL m)
{
    return f[n]*inv(f[m])%Mod*inv(f[n-m])%Mod;
}
int main()
{
    init();
    int t;sd(t);
    while(t--)
    {
        int n,m,k;sddd(n,m,k);
        if(m+k > n) printf("0\n");
        else
        {
            LL ma1 = C(n,k)*inv(quick_mi(2,n))%Mod;
            LL tmp = 0;
            for(int i=0;i<m;++i)
            {
                tmp = (tmp+C(n,i)*inv(quick_mi(2,n))%Mod)%Mod;
            }
            tmp = (1-tmp+Mod)%Mod;
            LL ans = ma1*inv(tmp)%Mod;
            plr(ans);
        }
    }
    system("pause");
    return 0;
}

A:树形dp.(注意不包括路径上的点的权值)
dp[i]表示i点向下的最大价值。
对面每个点有两种情况
1.以这个点为中间媒介,这个点的两条子节点上的边相连为最大.
2.以这个点为起点，和向下的某条子节点边上的点相连为最大.

所以边更新dp值边进行比较，同时最后比较自己为起点,那么dp[i]显然就是i点往下的最大价值了,注意的是,这个dp[i]在最后更新完时显然已经将和子节点的边的权值计算在内。
然后dp[i]也可能是a[i],所以最后还要更新一下。

Code:

struct Node{int to,dis;};
LL a[N],dp[N],ans;
vector<Node> G[N];
void dfs(int u,int fa)
{
    for(auto t:G[u])
    {
        int v = t.to,d = t.dis;
        if(v == fa) continue;
        dfs(v,u);
        ans = max(ans,dp[u]+dp[v]+d);//以u为中间媒介,通过之前更新的最大dp[u]来更新dp[v].
        dp[u] = max(dp[u],dp[v]+d);//以v或者v以下的点为终点;显然dp[v]已经与a[v]比较过;
    }
    ans = max(ans,dp[u]+a[u]);//以u为起点
    dp[u] = max(dp[u],a[u]);
}
int main()
{
    int t;sd(t);
    while(t--)
    {
        ans = -INF;
        int n;sd(n);
        for(int i=1;i<=n;++i) G[i].clear(),dp[i] = -INF;
        for(int i=2;i<=n;++i)
        {
            int x,y;sdd(x,y);
            G[i].push_back(Node{x,y});
            G[x].push_back(Node{i,y});
        }
        for(int i=1;i<=n;++i) sld(a[i]);
        dfs(1,0);
        plr(ans);
    }
  //  system("pause");
    return 0;
}