제출 #852816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852816		Denkata	Star Trek (CEOI20_startrek)	C++14	0 / 100	8 ms	8880 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxd = 1e5+3;
const int maxn = 1e5+3;
ll i,j,p,q,n,m,k,d,ans,dp[maxd][4],cnt1,cnt0,br[maxn][2],kraen[maxn],dist[maxn],winner[maxn],tek[maxn];
vector <int> v[maxn];
void dfs(int u,int p)
{
    kraen[u] = 0;
    for(auto i:v[u])
    {
        if(i==p)continue;
        dist[i] = dist[u]+1;
        dfs(i,u);
        if(kraen[i]==0)
            kraen[u] = 1;
    }
}
void dfs2(int u,int p)
{
    tek[u] = 0;
    for(auto i:v[u])
    {
        if(i==p)continue;
        dfs2(i,u);
        if(tek[i]==0)
            tek[u] = 1;
    }
}
void dfs3(int u,int p,int who)
{
    if(who==1)
        dp[1][kraen[u]]++;
    if(who==0)
    {
        if(kraen[u]==1)
            dp[1][2]++;
        if(kraen[u]==0)
            dp[1][3]++;
    }
    for(auto i:v[u])
    {
        if(i==p)
            continue;
        dfs3(i,u,(who^1));
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>d;
    d++;
    for(i=1; i<n; i++)
    {
        cin>>p>>q;
        v[p].push_back(q);
        v[q].push_back(p);
    }
    dfs(1,0);
    /**
    for(i=1;i<=n;i++)
        cout<<i<<" : "<<kraen[i]<<endl;
    */
    for(i=1;i<=n;i++)
    {
        dfs2(i,0);
        if(tek[i]==1)
            winner[i] = 1,cnt1++;
        else winner[i] = 0,cnt0++;
        //cout<<winner[i]<<endl;
    }
    dfs3(1,0,1);
    //cout<<cnt0<<" "<<cnt1<<endl;
    for(i=2; i<=d; i++)
    {
        dp[i][1] = dp[i-1][3]*cnt1+(dp[i-1][0]+dp[i-1][1])*cnt0;
        dp[i][2] = dp[i-1][0]*cnt1+(dp[i-1][2]+dp[i-1][3])*cnt0;
        dp[i][0] = dp[i-1][0]*cnt1+(dp[i-1][2]+dp[i-1][3])*cnt0;
        dp[i][3] = dp[i-1][3]*cnt1+(dp[i-1][0]+dp[i-1][1])*cnt1;
    }
    //cout<<dp[1][0]<<" "<<dp[1][1]<<" "<<dp[1][2]<<" "<<dp[1][3]<<endl;
    cout<<(dp[1][1]+dp[1][0])*cnt0<<endl;

    ///
    return 0;
}
/**
12 2
1 2
2 4
2 5
5 8
1 3
3 6
3 7
6 9
7 10
10 11
10 12
*/

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