题目链接
https://codeforces.com/contest/516/problem/D
题解
我还是数据结构水平太低了啊……连一个点子树内距离不超过(l)的点数都不会求
首先有一个熟知的结论是，我们任取原树的一条直径，那么对于任何一个点，直径的两端点中至少有一个到它的距离等于它到所有点的最远距离。
假设直径是((u_d,v_d)), 那么我们就把(u)的最远距离的式子化简成了(f_u=max(dis(u,u_d),dis(u,v_d)). 考虑(u_d)和(v_d)分别贡献给哪些点，可以发现一条特殊的边——直径的“中边”，设这条边是((u_m,v_m))其中(u_m)离(u_d)更近，则这条边(u_m)一侧的所有点的(f)都是等于和(v_d)的距离，(v_m)一侧的所有点的(f)都等于和(u_d)的距离。
我们可以把上面的结论简化一下：以(f_u)最小的点(u)为根，则任何一个点的儿子的(f)值大于该点的(f)值，然后我们只需要求出每个点(u)子树内有多少个点(f)值不超过(f_u+l). 这样和上面显然是等价的，但是变简单了（不需要讨论两边子树）。
现在的问题就是如何对每个点(u)求出(f_u).
考虑每个点能贡献到哪里，在DFS时维护栈，由于栈上的元素(f)值是单调的，因此可以二分。注意双指针复杂度是错的。
时间复杂度(O(qnlog n)).
官方题解还给了一种(O(qnalpha(n)+nlog n))的并查集做法。
代码
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define riterator reverse_iterator
using namespace std;
inline int read()
{
int x = 0,f = 1; char ch = getchar();
for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
return x*f;
}
const int N = 1e5;
struct Edge
{
int v,nxt; llong w;
} e[(N<<1)+3];
int fe[N+3];
int fa[N+3];
llong dis[N+3];
int ans[N+3];
int stk[N+3];
int n,q,en,rt,diau,diav,tp; llong l;
void addedge(int u,int v,int w)
{
en++; e[en].v = v; e[en].w = w;
e[en].nxt = fe[u]; fe[u] = en;
}
void dfs1(int u,int tfa)
{
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v; if(v==tfa) continue;
dis[v] = dis[u]+e[i].w;
dfs1(v,u);
}
}
void dfs2(int u,int tfa)
{
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v; if(v==tfa) continue;
dis[v] = dis[u]+e[i].w;
dfs2(v,u);
}
}
void dfs3(int u,int tfa,llong tdis)
{
dis[u] = max(dis[u],tdis);
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v; if(v==tfa) continue;
dfs3(v,u,tdis+e[i].w);
}
}
void dfs4(int u)
{
stk[++tp] = u;
int left = 0,right = tp;
while(left<right)
{
int mid = (left+right+1)>>1;
if(dis[stk[mid]]<dis[u]-l) {left = mid;}
else {right = mid-1;}
}
// printf("u=%d tp=%d pos=%d
",u,tp,left);
ans[u]++; ans[stk[left]]--;
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v; if(v==fa[u]) continue; fa[v] = u;
dfs4(v);
ans[u] += ans[v];
}
tp--;
}
int main()
{
scanf("%d",&n);
for(int i=1; i<n; i++) {int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w);}
dfs1(1,0);
for(int i=1; i<=n; i++) {if(dis[i]>dis[diau]) {diau = i;}}
dis[diau] = 0ll; dfs2(diau,0);
for(int i=1; i<=n; i++) {if(dis[i]>dis[diav]) {diav = i;}}
dfs3(diav,0,0ll);
for(int i=1; i<=n; i++) {if(rt==0||dis[i]<dis[rt]) {rt = i;}}
scanf("%d",&q);
while(q--)
{
scanf("%I64d",&l); for(int i=1; i<=n; i++) ans[i] = 0;
dfs4(rt);
int fans = 0; for(int i=1; i<=n; i++) fans = max(fans,ans[i]);
printf("%d
",fans);
}
return 0;
}