我的代码里MAX为1e6+100时候RE，MAX=2e6时AC ，MAX = 1e7的时候TLE。。。。。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define pr(x) cout<<#x<<":"<<x<<endl
const int MAX = 2e6;
const int INF = 1e9+100;
int N,M;
struct edge{
	int v,cost,next;
}Edge[MAX];
struct node{
	int val,pos;
};
int head[MAX];
int d[MAX];
int ecnt = 1;
int num[MAX];
node qmi[MAX];
node qmx[MAX];
int li,ri,lx,rx;
void add_edge(int u,int v,int cost)
{
	Edge[ecnt].v = v;Edge[ecnt].cost = cost;Edge[ecnt].next = head[u];
	head[u] = ecnt++;
}
int used[MAX];
void bfs(int u,int ds[])
{
	fill(ds,ds + N + 5,INF);
	memset(used,0,sizeof(used));
	ds[u] = 0;
	used[u] = 1;
	queue<int> Q;
	Q.push(u);
	while(!Q.empty())
	{
		int v = Q.front();Q.pop();
		for(int i = head[v];i;i = Edge[i].next)
		{
			int x = Edge[i].v;
			int c = Edge[i].cost;
			if(!used[x])
			{
				used[x] = 1;
				ds[x] = ds[v] + c;
				Q.push(x);
			}
		}
	} 
}
int main()
{
	scanf("%d%d",&N,&M);
	for(int i = 1;i <= N-1;i++)
	{
		int a,d;
		scanf("%d%d",&a,&d);
		add_edge(i+1,a,d);
		add_edge(a,i+1,d);
	}
	bfs(1,d);
	int mn = 0,target;
	for(int i = 1;i <= N;i++)
	{
		if(d[i] > mn)
		{
			mn = d[i];target = i;
		}
	}
	bfs(target,d);mn = 0;
	for(int i = 1;i <= N;i++)
	{
		num[i] = d[i];
		if(d[i] > mn)
		{
			mn = d[i];target = i;
		}
	}
	bfs(target,d);
	for(int i = 1;i <= N;i++) num[i] = max(num[i],d[i]);
	//单调队列
	int l = 1,r = 2;
	li = lx = 0;
	ri = rx = 1;
	qmx[0] = (node){num[1],1};
	qmi[0] = (node){num[1],1};
	int ans = 0;
	while(r <= N)
	{
		while(rx > lx && qmx[rx-1].val < num[r]) {rx--;}
		qmx[rx++] = (node){num[r],r};
		while(ri > li && qmi[ri-1].val > num[r]) {ri--;}
		qmi[ri++] = (node){num[r],r};
		while(qmx[lx].val - qmi[li].val > M)
		{
			l++;
			if(qmx[lx].pos < l) lx++;
			if(qmi[li].pos < l) li++;
		} 
		ans = max(ans,r-l+1);
		r++;
	}
	cout<<ans<<endl;
	
	return 0;
 } 

• Re:这题绝对有毒！ (34) NDCGZQBRKP 2017-09-27 19:02:43