欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

jzoj4279-[NOIP2015模拟10.29B组]树上路径【树形dp】

程序员文章站 2022-06-15 23:12:08
正题题目链接:https://gmoj.net/senior/#main/show/4279题目大意nnn个点的一棵树求经过每个点的最长路径。解题思路设fif_{i}fi​表示iii子树内的最长路径。我们第二次转移一个位置时我们枚举除了这个子树之外的其他子树,找到之外最大的fif_ifi​转移下去即可。因为数据保证了不会有菊花图所以能过codecodecode#include#include#include

正题

题目链接:https://gmoj.net/senior/#main/show/4279


题目大意

n n n个点的一棵树求经过每个点的最长路径。


解题思路

f i f_{i} fi表示 i i i子树内的最长路径。

我们第二次转移一个位置时我们枚举除了这个子树之外的其他子树,找到之外最大的 f i f_i fi转移下去即可。

因为数据保证了不会有菊花图所以能过


c o d e code code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10;
struct node{
	ll to,next,w;
}a[N*2];
ll n,tot,ls[N],f[N],g[N];
void addl(ll x,ll y,ll w){
	a[++tot].to=y;
	a[tot].next=ls[x];
	a[tot].w=w;
	ls[x]=tot;
	return;
}
void dfs(ll x,ll fa){
	f[x]=0;
	for(ll i=ls[x];i;i=a[i].next){
		ll y=a[i].to;
		if(y==fa)continue;
		dfs(y,x);
		f[x]=max(f[x],f[y]+a[i].w);
	}
	return;
}
void dp(ll x,ll fa,ll maxs){
	g[x]=f[x]+maxs;
	for(ll i=ls[x];i;i=a[i].next){
		ll y=a[i].to;
		if(y==fa)continue;
		ll z=maxs;
		for(ll j=ls[x];j;j=a[j].next)
			if(a[j].to!=fa&&a[j].to!=y){
				z=max(z,f[a[j].to]+a[j].w);
				g[x]=max(g[x],f[y]+f[a[j].to]+a[i].w+a[j].w);
			}
		dp(y,x,z+a[i].w);
	}
	return;
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%lld",&n);
	for(ll i=1;i<n;i++){
		ll x,y,w;
		scanf("%lld%lld%lld",&x,&y,&w);
		addl(x,y,w);addl(y,x,w);
	}
	dfs(1,1);
	dp(1,1,0);
	for(ll i=1;i<=n;i++)
		printf("%lld\n",g[i]);
}

本文地址:https://blog.csdn.net/Mr_wuyongcong/article/details/109239181

相关标签: dp jzoj 树形dp