bzoj 3677: [Apio2014]连珠线【树形dp】

参考：http://www.cnblogs.com/mmlz/p/4456547.html

枚举根，然后做树形dp，设f[i][1]为i是蓝线中点（蓝线一定是父子孙三代），f[i][0]为不是，转移很好想，但是这是n方的

考虑优化换根，记录最小值和最大值就能换根了

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

const int N=1000005,inf=1e9;

int n,h[N],cnt,f[N][2],fa[N],va[N],ans;

vector<int>s[N],g[N][2],b[N];

struct qwe

{

	int ne,to,va;

}e[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

inline void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

inline void ud(int x)

{

	if(x>ans)

		ans=x;

}

void dfs(int u)

{

	f[u][1]=-inf,f[u][0]=0;

	int fb=-inf,sb=-inf;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa[u])

		{

			va[e[i].to]=e[i].va;

			fa[e[i].to]=u;

			dfs(e[i].to);

			f[u][0]+=max(f[e[i].to][0],f[e[i].to][1]+e[i].va);

			int now=-max(f[e[i].to][0],f[e[i].to][1]+e[i].va)+f[e[i].to][0]+e[i].va;

			if(now>fb)

				sb=fb,fb=now;

			else if(now>sb)

				sb=now;

		}

	f[u][1]=f[u][0]+fb;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa[u])

		{

			int tmp=f[u][0]-max(f[e[i].to][0],f[e[i].to][1]+e[i].va),key;

			s[u].push_back(e[i].to);

			g[u][0].push_back(tmp);

			if(-max(f[e[i].to][0],f[e[i].to][1]+e[i].va)+f[e[i].to][0]+e[i].va==fb)

				key=sb;

			else

				key=fb;

			g[u][1].push_back(tmp+key);

			b[u].push_back(key);

		}

}

void dp(int u)

{

	for(int i=0,len=s[u].size();i<len;i++)

	{

		f[u][0]=g[u][0][i];

		f[u][1]=g[u][1][i];

		if(fa[u])

		{

			f[u][0]+=max(f[fa[u]][0],f[fa[u]][1]+va[u]);

			f[u][1]=f[u][0];

			int key=max(b[u][i],-max(f[fa[u]][0],f[fa[u]][1]+va[u])+f[fa[u]][0]+va[u]	);

			f[u][1]+=key;

		}

		ud(f[s[u][i]][0]+max(f[u][0],f[u][1]+va[s[u][i]]));

		dp(s[u][i]);

	}

}

int main()

{

	n=read();

	for(int i=1;i<n;i++)

	{

		int x=read(),y=read(),z=read();

		add(x,y,z),add(y,x,z);

	}

	dfs(1);

	ud(f[1][0]);

	dp(1);

	printf("%d\n",ans);

	return 0;

}