POJ 1849 树的直径或者树形dp(二)
ef long long ll; const int maxn=100100; int head[maxn],dp[maxn][3],tol; struct node{ int next,to,val; node(){}; node(int _next,int _to,int _val):next(_next),to(_to),val(_val){} }edge[3*maxn]; void add(int u,int v,int val){ edge[tol]=node(head[u],v,val); head[u]=tol++; } void dfs(int u,int fa){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa)continue; dfs(v,u); int ret[3]; for(int j=0;j<3;j++){ ret[j]=dp[u][j]; dp[u][j]=INF; } int tmp[3]={2*edge[i].val,edge[i].val,2*edge[i].val}; for(int j=2;j>=0;j--) for(int k=0;k<=j;k++) dp[u][j]=min(dp[u][j],ret[j-k]+dp[v][k]+tmp[k]); } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int i,j,k,m,n,p; while(~scanf("%d%d",&n,&m)){ memset(head,-1,sizeof(head)); tol=0; for(i=1;i