CF379F New Year Tree
题意翻译
你是一个程序猿，现在有一棵新年树（并不是传统的带着叶子的树）——它有四个节点： 1，2，3，4. 其中2，3，4的父亲都是1.
新年里，程序猿们往往会做一些有趣的事情。你则选择以往这棵树上加节点来取乐。 一个添加节点的操作是这样的：
1） 找到树上的一个叶子结点v
2） 设现在树上有n个节点，那么你现在会加入两个节点n+1和n+2，它们都会成为n的儿子.
你的任务是在做q次这样的操作，并在每做完一次后计算一次树的直径。来吧，我们一起来解决这道新年问题吧！
输入：
第一行一个整数\(q (1 ≤ q ≤ 5×10^5)\) ,表示操作次数。接下来q行，每行一个数v，表示你当前操作的节点。保证它一定是一个叶子结点。
输出：
q行，每行一个数，表示做了这个操作以后树的直径。
有一个小结论就是在合并两个树的时候
新合并出来的树的直径的两个端点一定是两个原树的直径的端点,因为只有6种方案,所以暴力判断一下就好了
先离线处理出整棵树,合并时用并查集合并
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 1000005 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m , hea[M] , num , q[M] , dep[M] , st[M][20] ;
int l[M] , r[M] , to[M] , f[M] , Res[M] ;
struct E { int Nxt , to ; } edge[M << 1] ;
inline void add_edge(int from , int to) {
edge[++num].Nxt = hea[from] ;
edge[num].to = to ; hea[from] = num ;
}
int find(int x) { if(f[x] != x) f[x] = find(f[x]) ; return f[x] ; }
void Dfs(int u , int father , int depth) {
dep[u] = depth ; st[u][0] = father ;
for(int i = hea[u] , v ; i ; i = edge[i].Nxt) {
v = edge[i].to ;
if(v == father) continue ;
Dfs(v , u , depth + 1) ;
}
}
inline void ST() {
for(int j = 1 ; j <= 19 ; j ++)
for(int i = 1 ; i <= n ; i ++)
st[i][j] = st[st[i][j - 1]][j - 1] ;
}
inline int LCA(int u , int v) {
if(dep[u] < dep[v]) swap(u , v) ;
for(int i = 19 ; i >= 0 ; i --)
if(dep[st[u][i]] >= dep[v])
u = st[u][i] ;
if(u == v) return u ;
for(int i = 19 ; i >= 0 ; i --)
if(st[u][i] != st[v][i])
u = st[u][i] , v = st[v][i] ;
return st[u][0] ;
}
int u , v , Ans , el , er , d ;
inline void Solve(int x , int y) {
u = find(x) , v = find(y) ;
Ans = 0 , el = 0 , er = 0 , d = 0 ;
Ans = dep[l[u]] + dep[r[u]] - (dep[LCA(l[u] , r[u])] << 1) , el = l[u] , er = r[u] ;
d = dep[l[v]] + dep[r[v]] - (dep[LCA(l[v] , r[v])] << 1) ;
if(d > Ans) Ans = d , el = l[v] , er = r[v] ;
d = dep[l[u]] + dep[l[v]] - (dep[LCA(l[u] , l[v])] << 1) ;
if(d > Ans) Ans = d , el = l[u] , er = l[v] ;
d = dep[l[u]] + dep[r[v]] - (dep[LCA(l[u] , r[v])] << 1) ;
if(d > Ans) Ans = d , el = l[u] , er = r[v] ;
d = dep[l[v]] + dep[r[u]] - (dep[LCA(l[v] , r[u])] << 1) ;
if(d > Ans) Ans = d , el = l[v] , er = r[u] ;
d = dep[r[u]] + dep[r[v]] - (dep[LCA(r[u] , r[v])] << 1) ;
f[v] = u ; l[u] = el , r[u] = er ;
}
int main() {
m = read() ; n = 1 ;
q[1] = 1 ; q[2] = 1 ;
to[1] = ++ n ; add_edge(1 , to[1]) ; add_edge(to[1] , 1) ;
to[2] = ++ n ; add_edge(1 , to[2]) ; add_edge(to[2] , 1) ;
to[3] = ++ n ; add_edge(1 , to[3]) ; add_edge(to[3] , 1) ;
for(int i = 3 ; i <= m + 2 ; i ++) {
q[i] = read() ;
to[i * 2 - 1] = ++ n ; add_edge(q[i] , to[i * 2 - 1]) ; add_edge(to[i * 2 - 1] , q[i]) ;
to[i << 1] = ++ n ; add_edge(q[i] , to[i << 1]) ; add_edge(to[i << 1] , q[i]) ;
}
for(int i = 1 ; i <= n ; i ++) f[i] = i , l[i] = i , r[i] = i ;
Dfs(1 , 1 , 1) ; ST() ;
for(int i = 1 ; i <= m + 3 ; i ++) {
Solve(q[i] , to[i * 2 - 1]) ;
if(i == 2) continue ;
Solve(q[i] , to[i << 1]) ;
if(i > 2) {
int u = find(q[i]) ;
Res[i - 2] = dep[l[u]] + dep[r[u]] - (dep[LCA(l[u] , r[u])] << 1) ;
}
}
for(int i = 1 ; i <= m ; i ++) printf("%d\n",Res[i]) ;
return 0 ;
}1、2019阿里巴巴面试题集锦(有答案哦)，收藏！
2、ChartDirector Linux下中文显示问题
3、IIS 7.5 配置伪静态
4、随谈---------多年之后，我又回来了
5、asp.net中的加密方法