BZOJ 2500 幸福的道路 樹形DP+單調隊列

BZOJ 2500 幸福的道路 樹形DP+單調隊列

題目大意：給定一棵樹，令a[i]為從第i個節點出發的最長鏈，求a[i]中最長的區間，滿足區間內最大值與最小值之差不超過m

讀錯題害死人，腦殘害死人

求a[i]顯然是樹形DP

考慮從一個點出發的鏈可以從子節點走，也可以從父節點走

因此我們DP兩次，第一次求出從子節點走的最長鏈，第二次求出從父節點走的最長鏈，兩次取max就是答案

但是直接DP會有問題，因為從父節點走的最長鏈可能是從自己的子樹出發的，這樣就會走重

因此除記錄從子節點出發的最長鏈外還要記錄一個從另一個子節點出發的次長鏈，如果最長鏈長度相同就從次長鏈走即可

第二問用單調隊列隨便搞搞就好了

時間復雜度O(n)

#include 
#include 
#include 
#include 
#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<