제출 #557701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557701		status_coding	Star Trek (CEOI20_startrek)	C++14	50 / 100	1084 ms	14748 KiB

startrek

#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

struct nodS
{
    bool dp;
    int nrFChild, nrCrit;
    vector<int> v;
};

long long put(long long baza, long long exp)
{
    if(!exp)
        return 1;

    long long ans = put(baza, exp/2);
    ans *= ans;
    ans %= mod;

    if(exp % 2)
    {
        ans *= baza;
        ans %= mod;
    }

    return ans;
}

long long n,d;

nodS nod[100005];

bool win[100005];
long long nrCrit[100005];

long long dp[100005];

void addChild(int p, int it)
{
    if(!nod[it].dp)
    {
        nod[p].nrFChild ++;
        nod[p].dp = true;
    }
}

void dfs(int p, int par)
{
    nod[p].nrFChild = 0;
    nod[p].nrCrit = 0;

    for(int it : nod[p].v)
    {
        if(it == par)
            continue;

        dfs(it, p);

        addChild(p, it);
    }

    nod[p].dp = (nod[p].nrFChild > 0);

    if(!nod[p].dp)
        nod[p].nrCrit = 1;
    else
        nod[p].nrCrit = 0;

    for(int it : nod[p].v)
    {
        if(it == par)
            continue;

        if(nod[p].dp && !nod[it].dp && nod[p].nrFChild == 1)
            nod[p].nrCrit += nod[it].nrCrit;

        if(!nod[p].dp && nod[it].dp)
            nod[p].nrCrit += nod[it].nrCrit;
    }
}

int main()
{
    cin>>n>>d;

    if(n == 2)
    {
        cout<<put(n, 2*d);
        return 0;
    }

    for(int i=1;i<n;i++)
    {
        int x, y;
        cin>>x>>y;

        nod[x].v.push_back(y);
        nod[y].v.push_back(x);
    }

    for(int i=1;i<=n;i++)
    {
        dfs(i, 0);

        win[i] = nod[i].dp;
        nrCrit[i] = nod[i].nrCrit;
    }

    for(int i=1;i<=n;i++)
    {
        if(!win[i])
            dp[i] = 1;
    }

    for(int i=d-1 ;i>=0; i--)
    {
        long long nrF=0;

        for(int j=1;j<=n;j++)
        {
            nrF += dp[j];
            nrF %= mod;
        }

        long long nrW = put(n, 2*(d-i-1) + 1 ) - nrF + mod;
        nrW %= mod;

        //cout<<nrW<<' '<<nrF<<'\n';

        for(int j=1;j<=n;j++)
        {
            if(!win[j])
            {
                dp[j] = (n - nrCrit[j]) * (nrF + nrW);
                dp[j] %= mod;

                dp[j] += nrCrit[j] * nrW;
                dp[j] %= mod;
            }
            else
            {
                dp[j] = nrCrit[j] * nrF;
                dp[j] %= mod;
            }
        }
    }

    cout<<(put(n, 2*d) - dp[1] + mod) % mod;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15