[Noip2016]天天愛跑步 LCA+DFS

[Noip2016]天天愛跑步

小c同學認為跑步非常有趣,于是決定制作一款叫做《天天愛跑步》的遊戲。?天天愛跑步?是一個養成類遊戲,需要玩家每天按時上線,完成打卡任務。這個遊戲的地圖可以看作一一棵包含 N個結點和N-1 條邊的樹, 每條邊連接配接兩個結點,且任意兩個結點存在一條路徑互相可達。樹上結點編号為從1到N的連續正整數。現在有個玩家,第個玩家的起點為Si ,終點為Ti  。每天打卡任務開始時,所有玩家在第0秒同時從自己的起點出發, 以每秒跑一條邊的速度,不間斷地沿着最短路徑向着自己的終點跑去, 跑到終點後該玩家就算完成了打卡任務。 (由于地圖是一棵樹, 是以每個人的路徑是唯一的)小C想知道遊戲的活躍度, 是以在每個結點上都放置了一個觀察員。 在結點的觀察員會選擇在第Wj秒觀察玩家, 一個玩家能被這個觀察員觀察到當且僅當該玩家在第Wj秒也理到達了結點J  。 小C想知道每個觀察員會觀察到多少人?注意: 我們認為一個玩家到達自己的終點後該玩家就會結束遊戲, 他不能等待一 段時間後再被觀察員觀察到。 即對于把結點J作為終點的玩家: 若他在第Wj秒重到達終點,則在結點J的觀察員不能觀察到該玩家;若他正好在第Wj秒到達終點,則在結點的觀察員可以觀察到這個玩家。

第一行有兩個整數N和M 。其中N代表樹的結點數量, 同時也是觀察員的數量, M代表玩家的數量。

接下來n-1 行每行兩個整數U和V ,表示結點U 到結點V 有一條邊。

接下來一行N 個整數,其中第個整數為Wj , 表示結點出現觀察員的時間。

接下來 M行,每行兩個整數Si和Ti,表示一個玩家的起點和終點。

對于所有的資料,保證 。

1<=Si,Ti<=N,0<=Wj<=N

輸出1行N 個整數,第個整數表示結點的觀察員可以觀察到多少人。

6 3

2 3

1 2

1 4

4 5

4 6

0 2 5 1 2 3

1 5

1 3

2 6

2 0 0 1 1 1

對于1号點，W1=0，故隻有起點為1号點的玩家才會被觀察到，是以玩家1和玩家2被觀察到，共2人被觀察到。

對于2号點，沒有玩家在第2秒時在此結點，共0人被觀察到。

對于3号點，沒有玩家在第5秒時在此結點，共0人被觀察到。

對于4号點，玩家1被觀察到，共1人被觀察到。

對于5号點，玩家1被觀察到，共1人被觀察到。

對于6号點，玩家3被觀察到，共1人被觀察到。

題解：一年前多的題了，不過現在再做的話已經不是那個難度了。

想法有點古怪，直接上做法吧：

對于玩家a->b，設a,b的lca是c，路徑長度是len，那麼路徑可以拆成2半，如果觀察員i想看到第一半，那麼要求dep[a]-dep[i]=w[i]->dep[a]=dep[i]+w[i]，且i是a的祖先；如果i想看到第二半，那麼要求len-(dep[b]-dep[i])=w[i]->len-dep[b]=w[i]-dep[i]，且i是b的祖先。當然，還有一個要求，就是i在c的子樹中，但是我們先不考慮這個。那麼做法如下：

在DFS通路到x時，先記錄之前有多少點的dep[a]=dep[x]+w[x]以及len-dep[b]=w[x]-dep[x]（用桶即可），記為ans1，然後周遊x的子樹，周遊結束後，将x位置的玩家的dep[a]以及len-dep[b]加入到桶中，再查詢此時有多少點的dep[a]=dep[x]+w[x]以及len-dep[b]=w[x]-dep[x]，記為ans2，那麼ans2-ans1就是x的答案。

但是如果考慮到i在c的子樹中這個條件呢？也好辦，隻需要在c和c的父親中加入dep[a]和len-dep[b]，并且權值都是-1即可。

如果用tarjan求LCA，則時間複雜度是O(n)的，但是我懶啊~

|

歡迎來原網站坐坐！

>原文連結<