CF516D Drazil and Morning Exercise(up and down,并查集)

题目链接

CF

洛谷

题意简述

给定一棵 $n$ 个点带边权的树,定义 $d(u)$ 为树上离它最远的点到它的距离,$q$ 次询问,每次询问给定 $l$,求一个最大的树上连通块 $V’$ 的大小,满足 $\forall u, v\in V’$,$|d(u)-d(v)|\le l$。

$1\le n\le 10^5$, $1\le q\le 50$。

简要做法

首先使用 up and down(两遍 dfs,第一遍求往下走的最远距离,第二遍求往上走的最远距离)求出 $d(u)$。

有一个性质:如果以 $d(u)$ 最小的 $u$ 为根,$\forall v, d(v)\ge d(parent(v))$。(下文中的“子树”都是以 $d$ 最小的点为根的。)

简单证明

不难发现,我们只要证明 $u$ 的每个儿子 $v$ 都是子树 $v$ 中 $d$ 最小的,即可归纳地证明原命题。

假设子树 $v$ 中存在一个点 $w$,$d(w)<d(v)$,那么从 $v$ 出发的最长路的第一步一定是 $v$ 到 $w$ 的路径上的第一条边(否则的话,从 $w$ 出发可以走到 $v$ 再走从 $v$ 出发的最长路,就会导致 $d(w)>d(v)$),这样的话,从 $u$ 出发也可以先走到 $v$ 再走 $v$ 出发的最长路,这样的话 $d(u)>d(v)$,与题设矛盾。

题目所求的连通块一定是 $d$ 的大小连续的一段,令所求连通块中 $d$ 最小且离根最近的点为 $u$,由上面的性质不难发现,所求连通块一定在子树 $u$ 中。

如果按 $d$ 从大到小枚举每个点,用并查集维护符合条件的点的连通性以及每块的大小,可以发现,删去一个点(一个 $d>d(u)+l$ 的点)并不影响连通性,只需要将其所在块的大小减一即可。(加入一个点就是合并子树,删去一个点是删去叶子。)

这样的话答案就是过程中最大的一块的大小。

总时间复杂度就是 $O(qn\alpha(n)+n\log n)$ 或 O(qn+nlogn) 或 $O(qn\log n)$。

参考代码

(非常抱歉,使用了 CF 模板 qaq)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#ifndef OUUAN
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#endif
#include<bits/stdc++.h>

#define int LoveLive
//#define FAST_IOSTREAM 1

#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
#define SON(i,u)for(int i=head[u];i;i=nxt[i])
#define ms(a,x)memset(a,x,sizeof(a))
#define fi first
#define se second
#define pb emplace_back
#define pq priority_queue
#define isinf(x)(x>=INF?-1:x)
#define y1 why_is_there_a_function_called_y1
#define DEBUG(x)cerr<<(#x)<<":"<<x<<endl
using namespace std;
typedef long long LoveLive;typedef pair<int,int>pii;typedef vector<int>vi;
#ifdef int
const int INF=0x3f3f3f3f3f3f3f3fll;
#else
const int INF=0x3f3f3f3f;
#endif
const double eps=1e-9;mt19937 rng(chrono::steady_clock::now().time_since_epoch().
count());int randint(int l,int r){int out=rng()%(r-l+1)+l;return out>=l?out:out+
r-l+1;}
#ifdef FAST_IOSTREAM
#define br cout<<'\n'
#define sp cout<<' '
long long read(){long long x;cin>>x;return x;}template<typename T>void read(T&x){
cin>>x;}template<typename T>void write(const T&x){cout<<x;}
#else
#define br putchar('\n')
#define sp putchar(' ')
template<typename T>typename enable_if<!is_integral<T>::value,void>::type read(T
&x){cin>>x;}long long read(){char c;long long out=0,f=1;for(c=getchar();!isdigit
(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())
out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T>typename enable_if
<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit
(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())
x=(x<<3)+(x<<1)+c-'0';return x*=f;}char read(char&x){for(x=getchar();isspace(x);
x=getchar());return x;}double read(double&x){scanf("%lf",&x);return x;}template<
typename T>typename enable_if<!is_integral<T>::value,void>::type write(const T&x
){cout<<x;}template<typename T>typename enable_if<is_integral<T>::value,void>::type
write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar
(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf
("%.10lf",x);}
#endif
template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args
...);}template<typename OutputIt,typename=typename enable_if<is_same<output_iterator_tag
,typename iterator_traits<OutputIt>::iterator_category>::value||(
is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value
&&!is_const<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first
!=__last;++__first)read(*__first);}template<typename InputIt,typename=typename enable_if
<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category
>::value>::type>void wts(InputIt __first,InputIt __last){bool isFirst=true;for(;
__first!=__last;++__first){if(isFirst)isFirst=false;else sp;write(*__first);}br;}
template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag
,typename iterator_traits<InputIt>::iterator_category>::value>::type>void wtb(InputIt
__first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}template
<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const
T&x){write(x);br;}template<typename T>void wte(const T&x){write(x);exit(0);}template
<typename T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}
template<typename T,typename...Args>void wtb(const T&x,Args...args){wts(x);wtb(args
...);}template<typename T,typename...Args>void wte(const T&x,Args...args){wts(x);
wte(args...);}template<typename T>inline bool up(T&x,const T&y){return x<y?x=y,1
:0;}template<typename T>inline bool dn(T&x,const T&y){return y<x?x=y,1:0;}

const int N = 100010;
const int mod = 1000000007;

int head[N], nxt[N << 1], to[N << 1], edge[N << 1], cnt;
int n, f[N], siz[N], id[N], rid[N];

struct Element
{
int fi, se;
Element() { fi = 0; se = -INF; }
void insert(int x)
{
if (x > fi)
{
se = fi;
fi = x;
}
else if (x > se) se = x;
}
int get(int x)
{
if (x == fi) return se;
return fi;
}
} dis[N];

void dfsdn(int u, int fa)
{
SON (i, u)
{
int v = to[i];
int w = edge[i];
if (v == fa) continue;
dfsdn(v, u);
dis[u].insert(dis[v].fi + w);
}
}

void dfsup(int u, int fa)
{
SON (i, u)
{
int v = to[i];
int w = edge[i];
if (v == fa) continue;
dis[v].insert(dis[u].get(dis[v].fi + w) + w);
dfsup(v, u);
}
}

void add(int u, int v, int w)
{
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
edge[cnt] = w;
}

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

void merge(int x, int y)
{
if (find(x) == find(y)) return;
if (siz[find(x)] < siz[find(y)]) swap(x, y);
siz[find(x)] += siz[find(y)];
f[find(y)] = find(x);
}

signed main()
{
#ifdef FAST_IOSTREAM
cin.sync_with_stdio(false);
cin.tie(0);
#endif

read(n);

For (i, 1, n - 1)
{
int u, v, w;
read(u, v, w);
add(u, v, w);
add(v, u, w);
}

dfsdn(1, 0);
dfsup(1, 0);

For (i, 1, n) id[i] = i;
sort(id + 1, id + n + 1, [](int x, int y){return dis[x].fi > dis[y].fi;});
For (i, 1, n) rid[id[i]] = i;

int q = read();

while (q--)
{
int len = read();
int l = 1;
int ans = 0;
For (i, 1, n)
{
f[i] = i;
siz[i] = 1;
}
For (u, 1, n)
{
while (dis[id[l]].fi > dis[id[u]].fi + len) --siz[find(id[l++])];
SON (i, id[u])
{
int v = to[i];
if (rid[v] < u) merge(id[u], v);
}
up(ans, siz[find(id[u])]);
}
wtb(ans);
}

return 0;
}