hdu 4714 (트 리 dp)
사고: 나 무 를 ans + 1 체인 으로 삭제 할 수 있 습 니 다. 정 답 은 ans + ans + 1 입 니 다.만약 에 한 노드 의 분기 수가 1 보다 많 으 면 이 점 과 부모 노드 의 변 을 삭제 하고 이 노드 가 형성 하 는 체인 수 는 바로 son - 1 이다.나무의 뿌리 노드 는 뿌리 노드 에 두 개의 가지 가 있어 야 합 니 다.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
const int N=1000100;
int head[N],num,ans;
struct edge
{
int ed,next;
}e[N*2];
void addedge(int x,int y)
{
e[num].ed=y;e[num].next=head[x];head[x]=num++;
e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
int dfs(int u,int fa)
{
int i,v,son=0;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(v==fa)continue;
son+=dfs(v,u);
}
if(son>=2)//
{
ans+=son-1;// son-1
if(u==1)ans--;//
return 0;
}
else return 1;
}
int main()
{
int i,x,y,n,t;
scanf("%d",&t);
while(t--)
{
memset(head,-1,sizeof(head));
num=0;
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
}
ans=0;
dfs(1,0);
printf("%d
",ans*2+1);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
