树形dp好题.
考虑到链一定是连续的,且在树上有两种情况:
蓝色表示,链上深度最浅的点是链的一端的情况.
而红色表示,链的两端都不是链上最浅的点.
而显然,对于蓝色的链,其最浅的点仍然可以向上拓展,而红色不行.
那么,问题就可以用树形dp解决了.
设f[u]表示以u为链的一端,且u为链上最浅的点的最长链的长度
这样我们就可以得到最长的蓝色链,转移方程也不难得出:$$f[u]=\max_{v\in son[u]} \{f[v]+len(v,u)\}$$
那么红色的呢?考虑到每一条红色链都能被它的最浅的点分成两条蓝色链,那么在决策点u时顺便更新答案即可(可见代码)
每个点u都只决策$|son[u]|$次,故总时间复杂度$O(n)$
#include<iostream>
#include<cstdio>
typedef long long ll;
#define MAXN 20011
void umax(ll &a,ll t)
{
if(t>a)a=t;
}
struct Edge
{
ll v,w,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
++cnt;
e[cnt].v=v,e[cnt].w=w;
e[cnt].nxt=last[u],last[u]=cnt;
}
ll f[MAXN],fa[MAXN],ans=0;
void dfs(ll u)
{
ll premax=0;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(v==fa[u])continue;
fa[v]=u;
dfs(v);
umax(ans,premax+f[v]+e[i].w);
umax(premax,f[v]+e[i].w);
}
f[u]=premax;
}
int main()
{
ll n;
scanf("%lld",&n);
for(ll i=1;i<n;++i)
{
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
adde(u,v,w);adde(v,u,w);
}
dfs(1);
printf("%lld",ans);
return 0;
}
y总,为什么我的图片挂了啊
可能是洛谷有限制吧,我刚刚看也挂了,现在好了。
把图片另存为下来,然后在题解里重新上传一下会比较保险。
我看也是挂了的,然后复制图片地址打开又好了
好奇妙啊,还是不行欸
统一回复:现已修好,问题好像是上传的图片名字中有下划线
好滴
y总,为啥我用unordered_map存图 用矩阵存边权会超内存,第6个case过不了,前面的能过逻辑应该没问题吧
unordered_map比较占内存。
一语惊醒梦中人呀
可能只是因为unordered_map和vector 需要更多的空间
发现一个错别字,$蓝色表示,链上深度最浅的点是链的一段 (一端)的情况。$
啊这,已修复
和我同种码风 爱了爱了