GMOJ3501 訊息傳遞

2022-09-23 05:12:21 字數 1718 閱讀 3221

h國的社會等級森嚴,除了國王之外,每個人均有且只有一個直接上級,當然國王沒有上級。如果a是b的上級,b是c的上級,那麼a就是c的上級。絕對不會出現這樣的關係:a是b的上級,b也是a的上級。

最開始的時刻是0,你要做的就是用1單位的時間把一個訊息告訴某一個人,讓他們自行散佈訊息。在任意一個時間單位中,任何一個已經接到訊息的人,都可以把訊息告訴他的一個直接上級或者直接下屬。

現在,你想知道:

1.到底需要多長時間,訊息才能傳遍整個h國的所有人?

2.要使訊息在傳遞過程中消耗的時間最短,可供選擇的人有那些?

洛谷p2018是這道題的弱化版,複雜度\(o(n^2)\)即可過。

樹形\(dp\)。分別列舉每一個點開始傳遞時的答案,然後取\(min\)。假設現在從\(i\)開始傳遞,那麼我們設\(i\)為樹根,要往葉子節點傳遞。

在以\(i\)為根的情況下,假設我們處理到以\(x\)為根的子樹,設\(f[i]\)表示處理完\(i\)為根的子樹的最少時間,那麼顯然應將\(x\)的兒子的\(f[i]\)從大到小的順序傳遞。

那麼有\[f[x]=min_(f[y]+ord[y])

\]其中\(ord[y]\)表示\(y\)的排名。

時間複雜度\(o(n^2\log n)\)。

先求出\(1\)為根時的答案,接下來換根即可。

維護每一個點的前字尾\(max\),從\(x\to y\)時,將\(1\sim ord[y]-1\)的\(min\)和\(ord[y]+1\sim cntson[x]\)的\(min-1\)求\(min\)即可。

時間複雜度\(o(n\log n)\)。

#include #include #include #include #include using namespace std;

const int n=200010;

int n,ans,tot,q[n],f[n],head[n],cnt[n];

vectorpos,maxn[n][3];

maprk[n];

struct edge

e[n*2];

bool cmp(int x,int y)

void add(int from,int to)

void solve(int x,int fa)

for (int i=cnt[x];i>=1;i--)

maxn[x][2].push_back(max(maxn[x][2][cnt[x]-i],f[q[i]]+i));

maxn[x][1].push_back(0); maxn[x][2].push_back(0);

}void dp(int x,int fa)

void dfs(int x,int fa)

else if (f[x]==ans) pos.push_back(x);

} for (int i=head[x];~i;i=e[i].next)

if (e[i].to!=fa) dfs(e[i].to,x);

if (x!=1) }

int main()

dp(1,0);

ans=f[1]; pos.push_back(1);

dfs(1,0);

sort(pos.begin(),pos.end());

printf("%d\n",ans+1);

for (int i=0;iprintf("%d ",pos[i]);

return 0;

}