hdu 4123 Bob’s Race (树的直径+尺取+rmq)(珍爱生命，远离log)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月17日 星期日 19时37分55秒
  4File Name :code/hdu/4123.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <map>
 14#include <cmath>
 15#include <string>
 16#include <cstdlib>
 17#include <ctime>
 18#define fst first
 19#define sec second
 20#define lson l,m,rt<<1
 21#define rson m+1,r,rt<<1|1
 22#define ms(a,x) memset(a,x,sizeof(a))
 23typedef long long LL;
 24#define pi pair < int ,int >
 25#define MP make_pair
 26#define log2 0.693147
 27using namespace std;
 28const double eps = 1E-8;
 29const int dx4[4]={1,0,0,-1};
 30const int dy4[4]={0,-1,1,0};
 31const int inf = 0x3f3f3f3f;
 32const int N=1E5+7; //双向边。。。
 33int n,Q;
 34int head[N];
 35int d[5][N];
 36bool vis[N];
 37int ans;
 38int cnt;
 39int dp[N][30],dp2[N][30];
 40int beg,lst;
 41int LOG[N+10];
 42struct Edge
 43{
 44    int v;
 45    int w;
 46    int nxt;
 47}edge[N];
 48void addedge( int u,int v,int w)
 49{
 50    edge[cnt].v = v;
 51    edge[cnt].w = w;
 52    edge[cnt].nxt = head[u];
 53    head[u] = cnt;
 54    cnt++;
 55}
 56void rmq_init()
 57{
 58    for ( int i = 1 ; i <= n ; i++)
 59	dp[i][0] = dp2[i][0] = d[0][i];
 60    for ( int j = 1 ;  (1<<j)<=n; j++)
 61	for ( int i = 1 ; i + (1<<j) -1 <= n ; i++)
 62	{
 63	    dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
 64	    dp2[i][j] = min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
 65	}
 66}
 67int rmq( int l,int r)
 68{
 69    if (l>r) return 0;
 70int k = log(double (r-l+1)/log2);
 71//int k = LOG[r-l+1];
 72//int k = 0;
 73//while (1<<(k+1)<=r-l+1) k++;
 74    int mx = max(dp[l][k],dp[r-(1<<k)+1][k]);
 75    int mn = min(dp2[l][k],dp2[r-(1<<k)+1][k]);
 76    return mx - mn;
 77}
 78void init()
 79{
 80    ms(head,-1);
 81    cnt = 0; 
 82}
 83void bfs( int s,int k)
 84{
 85    ms(d[k],0x3f);
 86    ms(vis,false);
 87    queue<int>q;
 88    q.push(s);
 89    vis[s] = true;
 90    d[0][s]  = 0;
 91    while (!q.empty())
 92    {
 93	int u = q.front();
 94	q.pop();
 95	for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
 96	{
 97	    int v = edge[i].v;
 98	    int w = edge[i].w;
 99	    if (vis[v]) continue;
100	    vis[v] = true;
101	    d[k][v] = d[k][u] + w;
102	    q.push(v);
103	}
104    }
105}
106void ruler(int k)
107{
108    int head = 1;
109    int tail = 1;
110    ans = 0 ;
111//    for ( int i = 1 ; i <= n ; i++) cout<<"d[0][i]:"<<d[0][i]<<endl;
112//   cout<<"k:"<<k<<endl;
113    while (tail<=n)
114    {
115	int cur = rmq(head,tail);
116//	cout<<"head:"<<head<<" tail:"<<tail<<" cur:"<<cur<<endl;
117	while (head<tail&&rmq(head,tail)>k) head++;
118	cur = rmq(head,tail);
119	if (cur<=k) ans = max(ans,tail-head);
120	tail++;
121    }
122    ans++;
123}
124void ruler2 ( int k)
125{
126    ans = 0 ;
127    int id = 1;
128    for ( int i = 1 ;i <= n ; i++)
129    {
130	while (id<=i&&rmq(id,i)>k) id++;
131	ans =max(ans,i-id+1);
132    }
133}
134int main()
135{
136	#ifndef  ONLINE_JUDGE 
137	freopen("code/in.txt","r",stdin);
138  #endif
139	LOG[0] = -1;
140	for ( int i = 1 ; i < 2* N ; i++) LOG[i] =LOG[i>>1]+1;
141	while (scanf("%d%d",&n,&Q),n||Q)
142	{
143	  //  cout<<log(2.0)<<endl;
144	    init();
145	    for ( int i = 1 ; i <= n-1 ; i++)
146	    {
147		int u,v,w;
148		scanf("%d%d%d",&u,&v,&w);
149		addedge(u,v,w);
150		addedge(v,u,w);
151	    }
152	    bfs(1,0);
153	    int far = 0 ;
154	    for ( int i = 1 ; i <= n ; i++)
155		if (d[0][i]>far)
156		{
157		    far = d[0][i];
158		    lst  = i ;
159		}
160	    far = 0 ;
161	    bfs(lst,1);
162	    for ( int i = 1 ;i  <= n ; i++)
163		if (d[1][i]>far)
164		{
165		    far = d[1][i];
166		    beg = i ;
167		}
168	    bfs(beg,2);
169	    for ( int i = 1 ; i <= n ; i++)
170		d[0][i] = max(d[1][i],d[2][i]);
171	     rmq_init();
172	    while (Q--)
173	    {
174		int x;
175		scanf("%d",&x);
176		ruler(x);
177		printf("%d\n",ans);
178	    }
179	}
180  #ifndef ONLINE_JUDGE  
181  fclose(stdin);
182  #endif
183    return 0;
184}
185v