T1 CF516D Drazil and Morning Exercise

• 给定一棵 n 个点的树，边有边权。
• 定义 \(f_x = \max_{i=1}^n \text{dist}(x,i)\)。
• q 次询问最大的满足 \(\max_{x \in s} f_x - \min_{x \in s} f_x \le l\) 的连通块 s 包含的点数。
• \(n \le 10^5，q \le 50\)。

solution

首先，两边dfs求出对于每个点的 \(f_x\) ，然后考虑以直径的中点作为根，那么在这个新的树里面，父亲的\(f\) 就会$ \le $ 儿子的\(f\) ，满足一种单调性，于是用类似双指针的东西维护一遍即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define int long long
inline int read()
{
   register int x = 0 , f = 0; register char c = getchar();
   while(c < '0' || c > '9') f |= c == '-' , c = getchar();
   while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48) , c = getchar();
   return f ? -x : x;
}
int n;
int fa[N] , up[N] , f[N] , g[N] , p[N] , siz[N];
struct node { int v , c; node(int v = 0 , int c = 0) : v(v) , c(c) {} };
vector< node > G[N];

void dfs1(int x , int Fa)
{
   int tmp;
   for(auto w : G[x]) if(w.v != Fa)
   {
   	dfs1(w.v , x);
   	tmp = f[w.v] + w.c;
   	if(tmp > f[x]) g[x] = f[x] , f[x] = tmp;
   	else if(tmp > g[x]) g[x] = tmp;
   }
}

inline bool cmp(const int &A , const int &B) { return f[A] == f[B] ? A < B : f[A] < f[B]; }

void dfs2(int x , int Fa)
{
   int tmp;
   for(auto w : G[x]) if(w.v != Fa)
   {
   	tmp = w.c + ((f[w.v] + w.c == f[x]) ? g[x] : f[x]);
   	if(tmp > f[w.v]) g[w.v] = f[w.v] , f[w.v] = tmp;
   	else if(tmp > g[w.v]) g[w.v] = tmp;
   	dfs2(w.v , x);
   }
   for(auto w : G[x]) if(cmp(x , w.v)) up[w.v] = x; else up[x] = w.v;
}

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void solve(int d)
{
   for(int i = 1 ; i <= n ; ++i) fa[i] = i , siz[i] = 1;
   int ans = 0;
   for(int i = n , j = n ; i >= 1 ; --i)
   {
   	while(f[p[j]] > f[p[i]] + d) --siz[find(p[j--])];
   	ans = max(ans , siz[p[i]]); siz[fa[p[i]] = up[p[i]]] += siz[p[i]];
   }
   cout << ans << '\n';
}

signed main()
{
   n = read(); int u , v , c;
   for(int i = 1 ; i < n ; ++i)
   	u = read() , v = read() , c = read() , G[u].push_back(node(v , c)) , G[v].push_back(node(u , c));
   dfs1(1 , 0); dfs2(1 , 0);
   for(int i = 1 ; i <= n ; ++i) p[i] = i;
   sort(p + 1 , p + 1 + n , cmp);
   int Q = read(); while(Q--)  solve(read());
   return 0;
}