Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：一棵树，定义 d[i] 为点 i 到树上某点的最大距离。给出若干查询，每个查询一个 x，问最多能有多少点满足这些点中，最大的 d 与最小的 d 的差小于等于 x。要求这些点的编号必须是连续的。
思路：可以三遍 bfs 处理出所有点的 d…
由于不能排序，所以就是尺取+rmq….
然而神 Tm TLE…
这复杂度还 TLE…
结果最后发现是 log 运算的常数太大被卡。
所以做法是先预处理一下，嗯。
珍爱生命，远离log!#
珍爱生命，远离log!#
珍爱生命，远离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}