【POJ3162】Walking Race 树形dp+单调队列+双指针

题目大意：给定一棵 N 个节点的无根树，边有边权，现生成一个序列 d，d[i] 表示 i 号节点到树上其他节点距离的最大值。给定一个 m，求 d 序列中最大值和最小值之差不超过 m 的最长连续段的长度是多少。

题解：d[i] 直接两次 dfs 即可，考虑如何求出最长连续段。可以发现若当前 [l,r] 合法，则 [l+1,r] 一定也合法，这意味着随着 l 的左移，r 不可能向右移动，符合双指针的思想。在双指针的基础之上维护两个单调队列，用来记录区间 [l,r] 的最大值和最小值，当不符合条件时，统计答案并将左端点右移。

代码如下

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+10;

int n,m,ans,dp[maxn][3];

int qmin[maxn],l1,r1,qmax[maxn],l2,r2;

struct node{

	int nxt,to,w;

	node(int a=0,int b=0,int c=0):nxt(a),to(b),w(c){}

}e[maxn<<1];

int tot=1,head[maxn];

inline void add_edge(int from,int to,int w){

	e[++tot]=node(head[from],to,w),head[from]=tot;

}

void dfs1(int u,int fa){

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to,w=e[i].w;

		if(v==fa)continue;

		dfs1(v,u);

		if(dp[u][0]<dp[v][0]+w){

			dp[u][1]=dp[u][0];

			dp[u][0]=dp[v][0]+w;

		}else{

			dp[u][1]=max(dp[u][1],dp[v][0]+w);

		}

	}

}

void dfs2(int u,int fa){

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to,w=e[i].w;

		if(v==fa)continue;

		if(dp[v][0]+w==dp[u][0])dp[v][2]=max(dp[u][1]+w,dp[u][2]+w);

		else dp[v][2]=max(dp[u][0]+w,dp[u][2]+w);

		dfs2(v,u);

	}

}

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=2;i<=n;i++){

		int to,w;scanf("%d%d",&to,&w);

		add_edge(i,to,w),add_edge(to,i,w);

	}

}

void solve(){

	dfs1(1,0),dfs2(1,0);

	l1=l2=1,r1=r2=0;

	int i,j;

	for(i=1,j=1;j<=n;j++){

		dp[j][0]=max(dp[j][0],dp[j][2]);

		while(l1<=r1&&dp[qmin[r1]][0]>=dp[j][0])--r1;

		while(l2<=r2&&dp[qmax[r2]][0]<=dp[j][0])--r2;

		qmin[++r1]=j,qmax[++r2]=j;

		if(dp[qmax[l2]][0]-dp[qmin[l1]][0]>m){

			ans=max(ans,j-i);

			i=min(qmax[l2],qmin[l1])+1;

			while(l1<=r1&&qmin[l1]<i)++l1;

			while(l2<=r2&&qmax[l2]<i)++l2;

		}

	}

	ans=max(ans,j-i);

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

}

int main(){

	read_and_parse();

	solve();

	return 0;

}