bzoj3677

题意：
在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 1 到 n。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子：
Append(w, v)：一个新的珠子 w 和一个已经添加的珠子 v 用红线连接起来。
Insert(w, u, v)：一个新的珠子 w 插入到用红线连起来的两个珠子 u,v 之间。具体过程是删去 u,v 之间红线，分别用蓝线连接 u,w 和 w,v。
每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。
给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。
你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。

#include
#include
#include
#include
#include
#define N 210000
#define inf 1e9
using namespace std;
struct node{int y,d,nex;}a[2*N];
int n,len,fir[N],f[N][2][2],tmp[2],g[3][3],h[3][3];
void ins(int x,int y,int d)
{a[++len].y=y;a[len].d=d;a[len].nex=fir[x];fir[x]=len;
}
void dp(int x,int fa,int d)
{for(int k=fir[x];k;k=a[k].nex){int y=a[k].y;if(y==fa) continue;dp(y,x,a[k].d);}for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)g[i][j]=-inf;tmp[0]=tmp[1]=-inf;tmp[0]=g[0][0]=0;for(int k=fir[x];k;k=a[k].nex){int y=a[k].y;if(y==fa) continue;tmp[1]=max(tmp[1]+f[y][0][0],tmp[0]+f[y][1][0]);tmp[0]+=f[y][0][0];for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)h[i][j]=-inf;for(int i=0;i<=2;i++)for(int j=0;j<=i;j++){h[i][j]=max(h[i][j],g[i][j]+f[y][0][0]);if(i<2){h[i+1][j]=max(h[i+1][j],g[i][j]+f[y][0][1]);h[i+1][j+1]=max(h[i+1][j+1],g[i][j]+f[y][1][1]);}}for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)g[i][j]=h[i][j];}for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)f[x][i][j]=-inf;for(int i=0;i<=1;i++){f[x][i][0]=max(f[x][i][0],tmp[i]);f[x][i][1]=max(f[x][i][1],tmp[i]+d);f[x][i][0]=max(f[x][i][0],g[1][i]+d);f[x][1][0]=max(f[x][1][0],g[2][i]);f[x][1][1]=max(f[x][1][1],g[2][i]+d);}int o=1;
}
int main()
{scanf("%d",&n);for(int i=1;iint x,y,d;scanf("%d%d%d",&x,&y,&d);ins(x,y,d);ins(y,x,d);}dp(1,0,-inf);printf("%d\n",max(f[1][0][0],f[1][1][0]));return 0;
}

题解：
别人的做法都是换根dp好厉害啊QAQ。。
考虑变蓝线的过程，最后一定能把蓝色的边分成若干长度为2的链(简称链)。又由于每个时刻图都是联通的，所以不合法情况就是：存在两个链的中心x，y，在删除这两条链的四条边后仍联通。如

然后发现如果全是直链必定合法，折链有特殊性。
具体来说就是，
折链的中心点之间必定是祖先关系。
如果一个点是中心点，那么有折链的子树到他的边一定要选。
简单的树形即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！