正題

題目鏈接:https://uoj.ac/problem/84

---

題目大意

有$n$個點的一棵樹，$1$為根，兩個人從根節點往下走（只能從深度小的點走到深度大的點）。

兩個人每一秒都可以一條邊（也可以不移動），或者不消耗時間將一個人傳送到另一個人那里。

求遍歷整棵樹需要的最少時間。

$1\le n\le 5\times 10^6$

---

解題思路

什么神仙題。

首先考慮到肯定存在一種方案使得一個人不需要使用傳送，因為顯然兩個人都需要使用傳送的方案可以通過交換兩個人的某些路徑得到有一個人不需要傳送的方案。

那么說明其中一個人的路徑肯定是一條鏈，我們將這個人稱之為本體，另一個人稱為分身。

然后一個粗暴的想法是$dp$出一條路徑，然后本體每走到一個點就等分身遍歷完除了鏈上的其他子樹再往下一個節點走。設$f_i$表示走到節點$i$的答案。

但是這樣顯然是會出問題的，對于節點$x$不一定是從它的父親處轉移的，因為兩個人可以同時移動，當分身最后一次傳送后本體可以和分身一起移動然后本體在下一個路口等分身傳送。

讓本體等分身是一種可能更賺的方案如圖（邊長代指了中間省略的點數量級別）

顯然當本體等待分身遍歷完$1～5$之后讓本體和分身分別走向$4$和$3$是更優的做法。

可以相當于在鏈上選擇一些關鍵點，本體只有在關鍵點時才等待，并且分身最后遍歷最深的葉子時本體同時出發。而關鍵點不連續的條件只有本體等分身的時才會出現，也就是分身最后遍歷的葉子深度比下一個關鍵點的深度要大。

而且顯然地如果出現了這種情況那么選擇另一個深度更小的祖先作為上一個關鍵點不可能更優（因為會走同一段）

所以我們只需要對于每個節點$x$找到第一個祖先$y$滿足$y$的子樹除去$x$的子樹后存在一個深度比$x$大的節點記為$s{f}_x$。

那么每個節點只需從$s{f}_x$轉移即可，如果找不到$sf$的節點顯然對于這樣的節點它的父節點只會有一個子節點，那么令$f_x=f_{f{a}_x}+1$即可。

問題是如何快速的求出每個$s{f}_x$，注意到對于一個處理好的子樹$x$只有可能有一段連續的鏈沒有$s{f}_x$（如圖紅色箭頭所指部分）

所以我們只需要從小往上處理維護每個處理好的子樹的$sf$為$0$的鏈。

然后兩棵子樹的時候我們直接暴力合并這些部分即可，因為合并完之后肯定只會留下長的那條鏈多出來的部分。

時間復雜度：$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e6+10; ll n,ans,deg[N],dep[N],fa[N],sf[N]; ll siz[N],sum[N],mx[N],nxt[N],f[N]; char s[N<<1]; void addl(ll x,ll y){deg[x]++;fa[y]=x;dep[y]=dep[x]+1;return; } signed main() {scanf("%lld",&n);if(n==1)return puts("0")&0;scanf("%s",s+1);for(ll i=1,now=0,cnt=0;i<=2*n;i++){if(s[i]=='(')++cnt,addl(now,cnt),now=cnt;else now=fa[now];}for(ll i=n;i>1;i--){if(!deg[i])siz[i]=1,sum[i]=mx[i]=dep[i];ll x,y;for(x=i;x&&dep[x]<=mx[fa[i]];x=nxt[x])sf[x]=fa[i];for(y=nxt[fa[i]];y&&dep[y]<=mx[i];y=nxt[y])sf[y]=fa[i];nxt[fa[i]]=x+y;sum[fa[i]]+=sum[i];siz[fa[i]]+=siz[i];mx[fa[i]]=max(mx[fa[i]],mx[i]);}f[1]=0;ans=n*n+100;for(ll i=2;i<=n;i++){f[i]=n*n+100;ll x=sf[i];if(x)f[i]=f[x]+sum[x]-sum[i]-dep[x]*(siz[x]-siz[i]);if(deg[fa[i]]==1)f[i]=min(f[i],f[fa[i]]+1);if(!deg[i])ans=min(ans,f[i]);}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的UOJ#84-[UR #7]水题走四方【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。