Codeforces Round #263 Appleman and Tree(트리 DP)
1931 단어 dpCodeforces
사고방식: 트리 DP.dp[u][0]는 이 노드를 포함하는 자수를 자른 후에 검은 노드가 하나도 없다는 것을 나타낸다. dp[u][1]는 이 노드를 포함하는 자수를 자른 후에 마침 검은 노드가 하나 있는 방법을 나타낸다.만약 이 노드가 검은색이라면 dp[u][0]는 0일 수밖에 없다.아들이 검은색이 있을 때는 아들과 잘라낼 수 있고, 아들이 검은색이 없을 때는 잘라내지 않는다.만약에 노드 u가 흰색이라면 이 노드가 있는 자수에 검은색을 가지게 하려면 이 검은색은 반드시 아들에게서 온 것이다.이 노드가 있는 노드가 검은색이 없도록 하려면 아들이 검은색이 없으면 자르지 않고 검은색이 있으면 자르세요.
상태 전환 방정식:
검은색 노드:
dp[u][1]=dp[u][1]*(dp[vv][1]+dp[vv][0])
흰색 노드:
dp[u][1]=dp[u][1]*(dp[vv][1]+dp[vv][0])+dp[u][0]*dp[vv][1]; dp[u][0]=dp[u][0]*(dp[vv][0]+dp[vv][1]);
코드는 다음과 같습니다.
#include
#include
#include
using namespace std;
const int maxn=200005;
const int mod=1000000007;
typedef long long ll;
struct Edge
{
int u,v,next;
}edge[maxn];
int tot;
int first[maxn];
int color[maxn];
void add(int uu,int vv)
{
edge[tot].u=uu;
edge[tot].v=vv;
edge[tot].next=first[uu];
first[uu]=tot++;
}
ll dp[maxn][2];
void dfs(int u,int fa)
{
if(color[u])
{
dp[u][0]=0;
dp[u][1]=1;
}
else
{
dp[u][1]=0;
dp[u][0]=1;
}
for(int i=first[u];i!=-1;i=edge[i].next)
{
int vv=edge[i].v;
if(vv==fa)continue;
dfs(vv,u);
if(color[u])
{
dp[u][1]=dp[u][1]*(dp[vv][1]+dp[vv][0])%mod;
}
else
{
dp[u][1]=dp[u][1]*(dp[vv][1]+dp[vv][0])%mod+dp[u][0]*dp[vv][1]%mod;
dp[u][1]%=mod;
dp[u][0]=dp[u][0]*(dp[vv][0]+dp[vv][1])%mod;
}
}
}
int main()
{
// freopen("data.txt","r",stdin);
tot=0;
memset(first,-1,sizeof(first));
int n;
scanf("%d",&n);
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
