出处: Codeforces
主要算法:LCA+树的直径
难度:4.4
思路分析:
给出q个操作,每次在一个节点上接上两个叶子。每一次询问树的直径。
暴力做法:每一次操作暴力BFS两遍……然而……复杂度时\(O(Q * 2n\),爆到不知哪里去了。
其实我们会发现,除非新加进来的两个点能够对直径产生影响,直径根本不会变。所以我们只需要考虑新加进来的点对原图的影响。
那么如何操作呢?先假设没经过任何操作之前,直径的端点时2和3(事实上2,3,4中任意两个都可以),设直径的端点1为A,端点2为B。每加进来两个点x,y时,若dist(x,A)或dist(x,B)大于原先的直径,则用它们更新,并且将直径的另一个端点设置为x或y。
下面来证明这样的做法的正确性:
由于在讲树的直径的时候我们提到过,从任意一个点出发进行BFS,所能到达的最远点一定是树的一个直径之一。
先假设新加进来的两个点x,y不存在,那么原先的树的直径就是A->B,并且一定是最长的了。设x,y的父亲节点为v。那么从v所能到达的最远的点一定是A或B。并且x或y到v的距离只有1,也只能是1。所以从x或y出发遍历所能够到达的最远的点一定也是A或B。而由于之前的直径是最长的,所以我当前的直径要比上一轮更长,只能是加了一,而这个1就是从x或y到v的距离的距离中产生的。
所以我们选择x来更新(因为x和y其实是一样的,你不可能有一条直径是从x到y的,因为这样只能是2,而刚开始就已经是2了)。分别求出x到A与B的距离,如果x到A更新成功,则B=x;如果x到B更新成功,则A=x;事实上,它们只有一个能更新成功。
于是现在问题就转化为了求两点之间距离了,LCA随便搞一搞就好了。这题还不用Dfs预处理,真是太可爱了……
代码注意点:
由于有q次操作,每次操作增加两个点,所以点的数目是\(2q+4\),而不是\(q+4\)
Code
/** This Program is written by QiXingZhi **/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int N = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
vector <int> G[N];
int dep[N],f[N][];
int Q,v,cur_node,A,B,cur1,cur2,ans,Tmp_Dist;
inline void AddEdge(int u, int v){
G[u].push_back(v);
G[v].push_back(u);
}
inline void Init(){
AddEdge(,), AddEdge(,), AddEdge(,);
cur_node = ;
A = , B = ;
ans = ;
f[][] = f[][] = f[][] = ;
dep[] = ;
dep[] = dep[] = dep[] = ;
}
inline void Update(int u, int v){
f[v][] = u;
dep[v] = dep[u] + ;
for(int i = ; (<<i) <= dep[v]; ++i){
f[v][i] = f[f[v][i-]][i-];
}
}
inline int LCA(int _a, int _b){
if(dep[_a] < dep[_b]){
swap(_a, _b);
}
int a = _a, b = _b;
for(int i = ; i >= ; --i){
if(dep[a] - (<<i) < dep[b]) continue;
a = f[a][i];
}
if(a == b) return a;
for(int i = ; i >= ; --i){
if(f[a][i] == f[b][i]) continue;
a = f[a][i];
b = f[b][i];
}
return f[a][];
}
inline int GetDist(int _a, int _b){
int __lca = LCA(_a, _b);
return dep[_a]-dep[__lca]+dep[_b]-dep[__lca];
}
int main(){
Init();
Q = r;
while(Q--){
v = r;
AddEdge(v,++cur_node);
Update(v,cur_node);
AddEdge(v,++cur_node);
Update(v,cur_node);
cur1 = cur_node;
Tmp_Dist = GetDist(cur1,A);
if(Tmp_Dist > ans){
ans = Tmp_Dist;
B = cur1;
}
Tmp_Dist = GetDist(cur1,B);
if(Tmp_Dist > ans){
ans = Tmp_Dist;
A = cur1;
}
printf("%d\n",ans);
}
/*
for(int i = 1; i <= cur_node; ++i){
for(int j = 0; j <= 3; ++j){
printf("f[%d][%d] = %d\n",i,j,f[i][j]);
}
}
for(int i = 1; i <= cur_node; ++i){
printf("dep[%d] = %d\n",i,dep[i]);
}
*/
return ;
}