BZOJ 2500 幸福的道路 树形DP+单调队列

题目大意：给定一棵树，令a[i]为从第i个节点出发的最长链，求a[i]中最长的区间，满足区间内最大值与最小值之差不超过m

读错题害死人，脑残害死人

求a[i]显然是树形DP

考虑从一个点出发的链可以从子节点走，也可以从父节点走

因此我们DP两次，第一次求出从子节点走的最长链，第二次求出从父节点走的最长链，两次取max就是答案

但是直接DP会有问题，因为从父节点走的最长链可能是从自己的子树出发的，这样就会走重

因此除记录从子节点出发的最长链外还要记录一个从另一个子节点出发的次长链，如果最长链长度相同就从次长链走即可

第二问用单调队列随便搞搞就好了

时间复杂度O(n)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1001001
using namespace std;
struct abcd{
	int to,f,next;
}table[M<<1];
int head[M],tot;
int n,m,ans;
long long f[M],g[M],h[M],a[M];
//f表示从子节点过来的最长链
//g表示从子节点过来的次长链
//h表示从父节点过来的最长链
void Add(int x,int y,int z)
{
	table[++tot].to=y;
	table[tot].f=z;
	table[tot].next=head[x];
	head[x]=tot;
}
void Tree_DP1(int x)
{
	int i;
	for(i=head[x];i;i=table[i].next)
	{
		Tree_DP1(table[i].to);
		if(f[table[i].to]+table[i].f>f[x])
			g[x]=f[x],f[x]=f[table[i].to]+table[i].f;
		else if(f[table[i].to]+table[i].f>g[x])
			g[x]=f[table[i].to]+table[i].f;
	}
}
void Tree_DP2(int x)
{
	int i;
	a[x]=max(f[x],h[x]);
	for(i=head[x];i;i=table[i].next)
	{
		long long temp=( f[x]==f[table[i].to]+table[i].f ? g[x] : f[x] );
		temp=max(temp,h[x]);
		h[table[i].to]=temp+table[i].f;
		Tree_DP2(table[i].to);
	}
}
void Monotonous_Queue()
{
	static int q_max[M],r_max,h_max;
	static int q_min[M],r_min,h_min;
	int i,j;
	for(j=0,i=1;i<=n;i++)
	{
		{
			int *q=q_max,&r=r_max,&h=h_max;
			while( r-h>=1 && a[i]>=a[q[r]] )
				q[r--]=0;
			q[++r]=i;
		}

		{
			int *q=q_min,&r=r_min,&h=h_min;
			while( r-h>=1 && a[i]<=a[q[r]] )
				q[r--]=0;
			q[++r]=i;
		}

		while(a[q_max[h_max+1]]-a[q_min[h_min+1]]>m)
		{
			++j;
			if(q_min[h_min+1]==j)
				q_min[++h_min]=0;
			if(q_max[h_max+1]==j)
				q_max[++h_max]=0;
		}

		ans=max(ans,i-j);
	}
}
int main()
{
	int i,x,y;
	cin>>n>>m;
	for(i=2;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		Add(x,i,y);
	}
	Tree_DP1(1);
	Tree_DP2(1);
	Monotonous_Queue();
	cout<<ans<<endl;
}

原文：http://blog.csdn.net/popoqqq/article/details/43954489