题目分析

考虑第一颗珠子（根）是谁，那么状态显然是f(x,0/1)，表示x是通过1操作加入的还是通过2操作加入的。如果是通过2操作加入的，那么边(x,father(x))和边(x,son(x))应该是蓝色的。
由此我们可以得到一个枚举根的 O(n2) O ( n 2 ) dp:　(y指的是x的儿子们,w指的是边的长度）
f(x,0)=∑max(f(y,0),f(y,1)+w(x,y)) f ( x , 0 ) = ∑ m a x ( f ( y , 0 ) , f ( y , 1 ) + w ( x , y ) )
f(x,1)=f(x,0)+max(f(y,0)+w(x,y)−max(f(y,0),f(y,0)+w(x,y))) f ( x , 1 ) = f ( x , 0 ) + m a x ( f ( y , 0 ) + w ( x , y ) − m a x ( f ( y , 0 ) , f ( y , 0 ) + w ( x , y ) ) )
考虑到我们可以通过两次dfs来完成 O(1) O ( 1 ) 移根，所以能够优化一维复杂度（详情参见树上每个点到离其最远点距离-dp做法），只用在记 f(y,0)+w(x,y)−max(f(y,0),f(y,0)+w(x,y)) f ( y , 0 ) + w ( x , y ) − m a x ( f ( y , 0 ) , f ( y , 0 ) + w ( x , y ) ) 最大值的同时记录一下这个的次大值，然后从父亲x到儿子y完成转移时，先减去y子树对f(x)造成的贡献，然后用类似的转移方法，只是当f(y,1)后面那一截取最大值时，若那个儿子恰好对应的是y，则只能取次大值进行dp。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
#define RI register int
const int N=200005,inf=0x3f3f3f3f;
int n,tot,ans;
int h[N],ne[N<<1],to[N<<1],w[N<<1];
int f[N],mx1[N],mx2[N],bj[N];
void add(int x,int y,int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void dfs1(int x,int las) {
mx1[x]=mx2[x]=-inf;//注意，可能并不能成为2操作加入的珠子
for(RI i=h[x];i;i=ne[i]) {
if(to[i]==las) continue;
dfs1(to[i],x);
RI kl=max(f[to[i]],f[to[i]]+mx1[to[i]]+w[i]);
f[x]+=kl,kl=f[to[i]]+w[i]-kl;
if(kl>=mx1[x]) mx2[x]=mx1[x],mx1[x]=kl,bj[x]=to[i];
else if(kl>mx2[x]) mx2[x]=kl;
}
}
void dfs2(int x,int las) {
ans=max(ans,f[x]);
for(RI i=h[x];i;i=ne[i]) {
if(to[i]==las) continue;
RI y=to[i];
RI kl=max(f[y],f[y]+mx1[y]+w[i]);//当前子树贡献，要减去
RI orzabs=max(f[x]-kl,f[x]-kl+(bj[x]==y?mx2[x]:mx1[x])+w[i]);//类似的dp法
f[y]+=orzabs,orzabs=f[x]-kl+w[i]-orzabs;
if(orzabs>=mx1[y]) mx2[y]=mx1[y],mx1[y]=orzabs,bj[y]=x;
else if(orzabs>mx2[y]) mx2[y]=orzabs;
dfs2(y,x);
}
}
int main()
{
RI x,y,z;
n=read();
for(RI i=1;i<n;++i)
x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
dfs1(1,0),dfs2(1,0);
printf("%dn",ans);
return 0;
}

最后

以上就是整齐小白菜为你收集整理的bzoj3677/洛谷P3647　连珠线　树形dp题目分析代码的全部内容，希望文章能够帮你解决bzoj3677/洛谷P3647　连珠线　树形dp题目分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。