(vijos 1892 noip 아날로그tree)
5731 단어 vijosnoip 시뮬레이션트리 DP
Solution
나중에 보충하지 않다
Code
입력이 vijos1892랑 달라요.
// by spli
#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=1010;
int n;
struct node{
int to,nxt;
}e[N<<1];int head[N],cnt;
bool vis[N];
LL ff[N],gg[N];
LL f[2][N];
LL g[2][N];
void add(int f,int t){
cnt++;
e[cnt]=(node){t,head[f]};
head[f]=cnt;
}
void dfs(int u,int fa){
g[0][u]=1;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
f[0][u]+=ff[v];
g[0][u]*=gg[v];
}
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
LL t=f[0][u]-ff[v]+f[0][v]+1;
LL p=g[0][u]/gg[v]*g[0][v];
if(f[1][u]==t) g[1][u]+=p;
else if(t>f[1][u]){
f[1][u]=t;g[1][u]=p;
}
}
if(f[1][u]>f[0][u]) ff[u]=f[1][u],gg[u]=g[1][u];
else if(f[0][u]>f[1][u]) ff[u]=f[0][u],gg[u]=g[0][u];
else ff[u]=f[1][u],gg[u]=g[0][u]+g[1][u];
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d",&n);
int u,num,x;
for(int i=1;i<=n;++i){
scanf("%d%d",&u,&num);
if(!num) vis[i]=1;
for(int j=1;j<=num;++j){
scanf("%d",&x);
add(u,x);
}
}
dfs(1,1);
if(f[1][1]>f[0][1])
cout<1][1]<1][1];
else if(f[1][1]==f[0][1]) cout<1][1]<1][1]+g[0][1];
else cout<0][1]<0][1];
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
(vijos 1892 noip 아날로그tree)전송문 Solution 나중에 보충하지 않다 Code 입력이 vijos1892랑 달라요....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.