题目大意：给一个树形图n个点（n-1条边），XXX要练习竞走，每次选定一个点k作为开始点，每次走从k开始能走的最长的一条路径（不要重边）。要求出最长的连续的这样的k，假设连续有kx个，前提：这样kx条路径的长度的任意两个值的差不超过m。
输入： n，m； 接下来n-1行数据，每一行两个整数fi,di。第i行表示 第i+1个点与fi连着一条长度为di的边。
不用想，稍微有一点点水平的朋友都能想到，首先对于每一个点，用一个树形dp求每个点能走到的最长路径长。
树形dp：
定义结构体： max1,max1from, max2。 //记录跟这个点有关的 最长路径长、最长路径长点， 第二最长路径长.
tree_dp1求出只走子树的边能到达的 max1,max1from, max2,max2from。
tree_dp2补上求出加上走向父节点的边能到达的 max1,max1from, max2。
第一步还是挺简单的，相信大多数人YY一下就可以搞定的。这样从每个点开始能走到的最长路径长maxlen就出来了。这个效率是O(n)的
然后需要做的是： 求出一个最长的连续区间，对这样区间上任意两个点i,j有 |maxlen[i] - maxlen[j]| <= m。
单调队列：
/**************************************************/
大家仔细看看这些星号就知道了。
（O(∩_∩)O~跟你开玩笑的，还是看163到179行的代码吧）
当然第二步也是很简单的，只是要写个水水的线段树作辅助。。。。这个效率最坏O(n)*log(n)+O(n)。
PS：个人觉得这第二步可以试试枚举起点，然后二分搜索区间终点，由于线段树查询效率为log(n)，所以总效率O(n)*log(n)*log(n)，再加上一些剪枝可以卡过的，可是……
没有可是了，擦擦，贡献了n个WA。
献上代码，与大家共勉！
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int maxn = ;
const int maxe = maxn*;
const int maxf = (<<)^(-); struct edge{
int u,v,c;
edge(int a=,int b=,int d=){ u=a, v=b, c=d; }
}e[maxe];
int head[maxn];
int next[maxe];
int cnt;
void add(int u,int v,int c){
e[cnt] = edge(u,v,c);
next[cnt] = head[u], head[u] = cnt++;
}
struct node{
int p, plen;
int max1,max1from;
int max2,max2from;
}no[maxn];
stack<int> iden;
int visited[maxn];
void tree_dp1(int root){
memset(visited,,sizeof(visited));
while(!iden.empty()) iden.pop();
iden.push(root);
int u,v=root;
no[root].p = , no[root].plen=;
no[v].max1 = no[v].max2 = ;
no[v].max1from = no[v].max2from = -;
while(!iden.empty()){
u = iden.top();
if(!visited[u]){
for(int i=head[u];i>=;i=next[i]){
v = e[i].v;
if(v == no[u].p) continue;
no[v].p = u; no[v].plen = e[i].c;
no[v].max1 = no[v].max2 = ;
no[v].max1from = no[v].max2from = -;
iden.push(v);
}
}
else{ //当前点u访问完毕
iden.pop();
for(int i=head[u];i>=;i=next[i]){
v = e[i].v;
if(v == no[u].p) continue;
int len = e[i].c + no[v].max1;
if(len > no[u].max1){
no[u].max2 = no[u].max1, no[u].max2from = no[u].max1from;
no[u].max1 = len; no[u].max1from = v;
}
else {
if(len > no[u].max2)
no[u].max2 = len, no[u].max2from = v;
}
}
}
visited[u] = ;
}
}
int maxlen[maxn];
void tree_dp2(int root){
while(!iden.empty()) iden.pop();
iden.push(root);
int u,v;
while(!iden.empty()){
u = iden.top(); iden.pop();
for(int i=head[u];i>=;i=next[i]){
v = e[i].v;
if(v == no[u].p) continue;
iden.push(v);
}
maxlen[u] = no[u].max1;
if(u != root){
int p = no[u].p,len;
if(no[p].max1from != u)
len = no[p].max1+no[u].plen;
else
len = no[p].max2+no[u].plen;
maxlen[u] = max(maxlen[u],len);
if(len > no[u].max1){
no[u].max2 = no[u].max1, no[u].max2from = no[u].max1from;
no[u].max1 = len; no[u].max1from = p;
}
else {
if(len > no[u].max2)
no[u].max2 = len, no[u].max2from = p;
}
}
}
}
void initial(){
cnt = ;
memset(head,-,sizeof(head));
}
struct segment{
int left,right;
int maxv,minv;
}a[maxn*];
void build(int left,int right,int k){
a[k].left=left, a[k].right=right;
a[k].minv = a[k].maxv = maxlen[left];
if(left < right){
int mid=(left+right)>>,k2=k<<;
build(left,mid,k2);
build(++mid,right,k2+);
a[k].minv = min(a[k2].minv,a[k2+].minv);
a[k].maxv = max(a[k2].maxv,a[k2+].maxv);
}
}
int query_min(int l,int r,int k){
if(l <= a[k].left && r >= a[k].right)
return a[k].minv;
int mid=(a[k].left+a[k].right)>>,k2=k<<;
int k3=k2+;
if(r <= mid)
return query_min(l,r,k2);
else {
if(l > mid)
return query_min(l,r,k3);
//else
return min(query_min(l,mid,k2),query_min(mid+,r,k3));
}
}
int query_max(int l,int r,int k){
if(l <= a[k].left && r >= a[k].right)
return a[k].maxv;
int mid=(a[k].left+a[k].right)>>,k2=k<<;
int k3=k2+;
if(r <= mid)
return query_max(l,r,k2);
else {
if(l > mid)
return query_max(l,r,k3);
//else
return max(query_max(l,mid,k2),query_max(mid+,r,k3));
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
initial();
int fi,di;
for(int i=;i<n;i++)
scanf("%d%d",&fi,&di), add(i+,fi,di), add(fi,i+,di);
//if(m < 0){ printf("0\n"); continue; }
int root = ;
tree_dp1(root);
//for(int i=1;i<=n;i++) printf("no[%d]: %d\t%d,\t %d\t%d\n",i,no[i].max1,no[i].max1from,no[i].max2,no[i].max2from);
tree_dp2(root);
build(,n,);
//for(int i=1;i<=n;i++) printf("no[%d]: %d\t%d,\t %d\t%d\n",i,no[i].max1,no[i].max1from,no[i].max2,no[i].max2from);
//for(int i=1;i<=n;i++) printf("maxlen[%d] = %d\n",i,maxlen[i]);
int ret = ;
int left=,right=;
int tpmin=maxlen[],tpmax=maxlen[];
while(left<=right && right<=n){
if(tpmax-tpmin <= m){
ret = max(ret,right-left+);
right++;
tpmin = min(tpmin,maxlen[right]);
tpmax = max(tpmax,maxlen[right]);
}
else {
left++;
tpmin = query_min(left,right,);
tpmax = query_max(left,right,);
}
if(ret > n - left) break;
}
printf("%d\n",ret);
}
return ;
}
单调队列核心:最大值的单调队列保持递减，最小值得单调队列保持递增！然后记录队列中每个最值的下标，使用left、right游标追赶。下面来个个人珍藏版代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int maxn = ;
const int maxe = maxn*;
const int maxf = (<<)^(-); struct edge{
int u,v,c;
edge(int a=,int b=,int d=){ u=a, v=b, c=d; }
}e[maxe];
int head[maxn];
int next[maxe];
int cnt;
void add(int u,int v,int c){
e[cnt] = edge(u,v,c);
next[cnt] = head[u], head[u] = cnt++;
}
void initial(){
cnt = ;
memset(head,-,sizeof(head));
} struct node{
int max1,max2; int max1from;
int p,pd,sc;
}no[maxn];
int visited[maxn];
void tree_dp1(int n,int root){
for(int i=;i<=n;i++) visited[i]=;
stack<int> st; st.push(root);
int u,v,d;
while(!st.empty()){
u=st.top();
//printf("u = %d, visited[u] = %d\n",u,visited[u]);
if(!visited[u]){
for(int i=head[u];i>=;i=next[i]){
v=e[i].v;
if(v == no[u].p) continue;
no[v].p=u, no[v].pd=e[i].c;
st.push(v);
}
visited[u]=;
}else {
for(int i=head[u];i>=;i=next[i]){
v=e[i].v;
if(v == no[u].p) continue;
d=e[i].c+no[v].max1;
if(d >= no[u].max1)
no[u].max2=no[u].max1, no[u].max1=d, no[u].max1from=v;
else if(d > no[u].max2)
no[u].max2=d;
}
st.pop();
}
}
}
void tree_dp2(int n,int root){
for(int i=;i<=n;i++) visited[i]=;
stack<int> st; st.push(root);
int u,v,p,d;
while(!st.empty()){
u=st.top();
//printf("u = %d, visited[u] = %d\n",u,visited[u]);
if(!visited[u]){
for(int i=head[u];i>=;i=next[i])
if(e[i].v != no[u].p)
st.push(e[i].v);
if(u != root){
p = no[u].p;
d = (no[p].max1from==u)?no[p].max2:no[p].max1;
d += no[u].pd;
if(d > no[u].max1) no[u].max2=no[u].max1, no[u].max1=d, no[u].max1from=p;
else if(d > no[u].max2) no[u].max2=d;
}
visited[u]=;
}else
st.pop();
}
}
int maxlen[maxn];
int dddl(int n,int M){
if(n <= ) return n;
if(M < ) return ;
deque<int> qmax,qmin; deque<int> idmax,idmin;
int ans=;
int left=,right=;
while(right <= n){
while(!qmax.empty() && maxlen[right] >= qmax.back())
qmax.pop_back(), idmax.pop_back();
qmax.push_back(maxlen[right]); idmax.push_back(right); while(!qmin.empty() && maxlen[right] <= qmin.back())
qmin.pop_back(), idmin.pop_back();
qmin.push_back(maxlen[right]); idmin.push_back(right);
while(qmax.front()-qmin.front() > M && left<right){
left++;
while(idmax.front() < left) idmax.pop_front(), qmax.pop_front();
while(idmin.front() < left) idmin.pop_front(), qmin.pop_front();
}
ans = max(ans,right-left+);
right++;
}
return ans;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
initial();
int fi,di;
for(int i=;i<n;i++)
scanf("%d%d",&fi,&di), add(i+,fi,di), add(fi,i+,di);
int root=;
tree_dp1(n,root);
tree_dp2(n,root);
for(int i=;i<=n;i++)
maxlen[i]=no[i].max1;
printf("%d\n",dddl(n,m));
}
return ;
}