Codeforces 337D Book of Evil 题解
题意
给定一个有$n$个结点的树,树上有$m (1\le m\le n\le10^5)$个结点被感染,分别是$p_1,p_2,\dots,p_m (1\le p_i\le n)$。
有一本“邪恶之书”在树上的某一个结点上,它可以感染 所有到它的距离小于等于$d (0\le d\le n-1)$的结点。
求“邪恶之书”可以在哪些结点上,使得它可以感染$p_1,p_2,\dots,p_m$这些结点。输出可能的个数。
题解
与树的直径类似。
从$1$号结点dfs
,找到距离它最远的感染结点$v_1$。
从$v_1$dfs
,找到距离它最远的感染结点$v_2$。
从$v_2$dfs
。
找到所有点$x$,使得到$v_1$和$v_2$的距离都小于等于$d$,输出个数即可。时间复杂度$O(n)$。
证明:
定义$D(x,y)$为结点$x$到结点$y$的距离。
设$x$为满足$D(v_1,x)\le d$且$D(v_2,x)\le d$的任意结点。
需要证明 不存在感染结点$v_3$,使得$D(v_3,x)>d$。
由求$v_1,v_2$的过程得:$v_1,v_2$是这棵树中,距离最大的两个感染结点(证明过程同树的直径的证明过程)。
若$D(v_1,x)\le d,D(v_2,x)\le d,D(v_3,x)>d$,则$D(v_1,v_3)>D(v_1,v_2)$,矛盾。
证毕。
程序
1 | // #pragma GCC optimize(2) |