[HDU2196] Computer(트리 dp)
제목 설명
전송문 제목: 나무의 점 하나하나에서 가장 먼 점까지의 거리를 구하세요.
문제풀이
비교적 고전적인 나무 모양 dp.나무의 지름 그 문제를 보았다면 dp 방법은 아주 좋았을 것이다 YY.maxn 및maxn은 점 i에서 하위 트리까지의 점 거리의 최대치와 차대치를 나타내고 f와 g는 점 i에서 하위 트리까지의 점 거리의 최대치와 하위 트리의 점이 아닌 점까지의 거리를 나타낸다.미루는 동안 그림 그려봐. YY.
코드
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int max_n=1e4+5;
const int max_e=max_n*2;
int n,x,y,z;
int tot,point[max_n],nxt[max_e],v[max_e],c[max_e];
int maxn[max_n],_maxn[max_n],f[max_n],g[max_n],ans[max_n];
inline void clear(){
tot=0;memset(point,0,sizeof(point));memset(nxt,0,sizeof(nxt));memset(v,0,sizeof(v));
for (int i=1;i<=n;++i) maxn[i]=_maxn[i]=f[i]=g[i]=ans[i]=0;
}
inline void add(int x,int y,int z){++tot;nxt[tot]=point[x];point[x]=tot;v[tot]=y;c[tot]=z;}
inline void treedp(int x,int fa){
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa){
treedp(v[i],x);
if (maxn[x]<maxn[v[i]]+c[i]){
_maxn[x]=maxn[x];
maxn[x]=maxn[v[i]]+c[i];
}
else _maxn[x]=max(_maxn[x],maxn[v[i]]+c[i]);
}
}
inline void get_ans(int x,int fa){
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa){
f[v[i]]=maxn[v[i]];
if (maxn[v[i]]+c[i]==maxn[x])
g[v[i]]=c[i]+max(g[x],_maxn[x]);
else
g[v[i]]=c[i]+ans[x];
ans[v[i]]=max(f[v[i]],g[v[i]]);
get_ans(v[i],x);
}
}
int main(){
while (scanf("%d",&n)!=EOF){
clear();
for (int i=2;i<=n;++i) scanf("%d%d",&x,&y),add(x,i,y),add(i,x,y);
treedp(1,0);
f[1]=ans[1]=maxn[1];
get_ans(1,0);
for (int i=1;i<=n;++i)
printf("%d
",ans[i]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.