c463 - apcs 樹狀圖分析 (Tree Analyses)
題目描述
題目給定一個樹狀圖，要求找出根節點以及所有節點到根節點的距離總和 H(T)。樹狀圖的輸入方式為，第一行給定節點數量 n，接下來 n 行描述每個節點的子節點。
解題思路
這題的核心是找出樹的根節點，並計算每個節點到根節點的深度。根節點的特點是它沒有父節點。程式碼使用深度優先搜尋 (DFS) 來計算每個節點的高度 (深度)，並同時找出根節點。DFS 從葉節點開始，向上追溯到根節點，更新每個節點的高度。最後，計算所有節點高度的總和，即為 H(T)。
複雜度分析
- 時間複雜度: O(N)，其中 N 是節點的數量。因為 DFS 遍歷了所有節點和邊緣一次。
- 空間複雜度: O(N)，主要用於儲存
fa陣列，該陣列儲存了每個節點的父節點和高度資訊。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
struct tree{
int pa,h=-1;
bool son;
}fa[100001];
long long int ans;
int root,n,k,t;
inline void dfs(int now,int hi){
if(fa[now].h>hi)return;
fa[now].h=hi;
if(fa[now].pa)
dfs(fa[now].pa,hi+1);
else root=now;
return;
}
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
n=read();
for(int i(1);i<=n;++i){
k=read();
if(!k)
fa[i].son=1;
while(k--){
t=read();
fa[t].pa=i;
}
}
for(int i(1);i<=n;++i)
if(fa[i].son)
dfs(i,0);
for(int i(1);i<=n;++i)
ans+=fa[i].h;
printf("%d\n%lld\n",root,ans);
}