題目描述

松鼠的新家是一棵樹，前幾天剛剛裝修了新家，新家有$n$ 個房間，并且有 $n?1$ 根樹枝連接，每個房間都可以相互到達，且倆個房間之間的路線都是唯一的。天哪，他居然真的住在“樹”上。

松鼠想邀請小熊維尼前來參觀，并且還指定一份參觀指南，他希望維尼能夠按照他的指南順序，先去 $a_1$，再去 $a_2$，……，最后到 $a_n$，去參觀新家。可是這樣會導致重復走很多房間，懶惰的維尼不停地推辭。可是松鼠告訴他，每走到一個房間，他就可以從房間拿一塊糖果吃。

維尼是個饞家伙，立馬就答應了。現在松鼠希望知道為了保證維尼有糖果吃，他需要在每一個房間各放至少多少個糖果。

因為松鼠參觀指南上的最后一個房間 $a_n$ 是餐廳，餐廳里他準備了豐盛的大餐，所以當維尼在參觀的最后到達餐廳時就不需要再拿糖果吃了。

輸入格式

第一行一個正整數 $n$，表示房間個數第二行 $n$ 個正整數，依次描述 $a_1,a_2,?,a_n$。

接下來 $n?1$ 行，每行兩個正整數 $x,y$，表示標號 $x$ 和 $y$ 的兩個房間之間有樹枝相連。

輸出格式

一共 $n$ 行，第 $i$ 行輸出標號為 $i$ 的房間至少需要放多少個糖果，才能讓維尼有糖果吃。

輸入輸出樣例 #1

輸入 #1

5
1 4 5 3 2
1 2
2 4
2 3
4 5

輸出 #1

1
2
1
2
1

說明/提示

對于全部的數據，$2 \le n \le 3 \time算法思路

樹結構構建：

使用鄰接表存儲樹結構（add函數）。
節點數$n$，訪問序列存儲在vis數組。
預處理階段：

DFS遍歷（dfs1函數）：從根節點（設為1）出發，計算每個節點的深度$de$和直接父節點$fa[i][0]$。

倍增預處理：計算每個節點的$2^j$級祖先，用于LCA查詢： $$fa[i][j]=fa[fa[i][j?1]][j?1](1\le j\le 20)$$

對數預處理：lg數組滿足$2^{\text{lg}[k]?1}\le k<2^{\text{lg}[k]}$，用于LCA跳躍優化。

LCA計算（lca函數）：

調整節點深度：若$de[a]<de[b]$，交換$a,b$。
將較深節點上跳到與較淺節點同一深度：
$$a=fa[a][\text{lg}[de[a]?de[b]]?1]$$
若此時$a=b$，返回$a$；否則同步上跳至LCA的子節點： $$a=fa[a][j],b=fa[b][j](j\text{從大到小枚舉})$$

最終LCA為$fa[a][0]$。

路徑標記與調整：

初始化：a[vis[1]] = 1。
遍歷訪問序列（$i$從2到$n$）：
對相鄰節點對$(vis[i?1],vis[i])$：
差分標記：b[vis[i-1]]++, b[vis[i]]++。
計算LCA（設為$js$）：b[js]–, b[fa[js][0]]–。
調整：a[vis[i-1]]–。
序列結束：a[vis[n]]–。
差分數組累加（dfs2函數）：

從葉子向根DFS，將子節點的$b$值累加到父節點： $$b[k]=b[k]+\sum _{\text{子節點}t}b[t]$$

最終答案：

對每個節點$i$，輸出$a[i]+b[i]$。
復雜度分析
時間：
DFS遍歷：$O(n)$
倍增預處理：$O(n\log n)$
$n?1$次LCA查詢：$O(n\log n)$
差分累加：$O(n)$
總時間復雜度：$O(n\log n)$
空間：$O(n\log n)$（存儲祖先數組）s 10^5$，$1\le a_i\le n$。

詳細代碼

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int h[N],fa[N][25];
int vis[N],lg[N],de[N];
int a[N],b[N];
int m,n,i,j,x,y,tot;
struct node{int w,to,ne;
}wc[N*2];
void add(int a,int b)
{tot++;wc[tot].w=a;wc[tot].to=b;wc[tot].ne=h[a];h[a]=tot;
}
void dfs1(int k)
{int s=h[k];while(s!=0){int t=wc[s].to;if(t!=fa[k][0]){fa[t][0]=k;de[t]=de[k]+1;dfs1(t);} s=wc[s].ne;}
}
int lca(int a,int b)
{if(de[a]<de[b]){int t=a;a=b;b=t;}while(de[a]!=de[b]){int k=lg[de[a]-de[b]]-1;a=fa[a][k];}if(a==b) return a;else{for(j=lg[de[a]]-1;j>=0;j--){if(fa[a][j]!=fa[b][j]){a=fa[a][j];b=fa[b][j];}}}return fa[a][0];
}
void dfs2(int k)
{int s=h[k];while(s!=0){int t=wc[s].to;if(t!=fa[k][0]){dfs2(t);b[k]+=b[t];}s=wc[s].ne;}
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(i=1;i<=n;i++)cin>>vis[i]; for(i=1;i<=n-1;i++){cin>>x>>y;add(x,y);add(y,x);}dfs1(1);for(j=1;j<=20;j++)for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];for(i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i?1:0);a[vis[1]]++;for(i=2;i<=n;i++){int js=lca(vis[i],vis[i-1]);b[vis[i]]++;b[vis[i-1]]++;b[js]--;b[fa[js][0]]--;a[vis[i-1]]--;}a[vis[n]]--;dfs2(1);for(i=1;i<=n;i++)cout<<a[i]+b[i]<<endl;return 0;
}