CH6303 天天愛跑步

6303 天天愛跑步 0x60「圖論」例題

小C同學認為跑步非常有趣，于是決定制作一款叫作《天天愛跑步》的遊戲。《天天愛跑步》是一個養成類遊戲，需要玩家每天按時上線，完成打卡任務。

這個遊戲的地圖可以看作一棵包含 n (n≤3*10^5) 個節點和 n-1 條邊的樹，任意兩個節點存在一條路徑互相可達。樹上節點的編号是 1~n 之間的連續正整數。

現在有 m (m≤3*10^5) 個玩家，第 i 個玩家的起點為 S_i，終點為 T_i。每天打卡任務開始時，所有玩家在第0秒同時從自己的起點出發，以每秒跑一條邊的速度，不間斷地沿着最短路徑向着自己的終點跑去，跑到終點後該玩家就算完成了打卡任務。因為地圖是一棵樹，是以每個人的路徑是唯一的。

小C想知道遊戲的活躍度，是以在每個節點上都放置了一個觀察員。在節點 j 的觀察員會選擇在第 W_j 秒觀察玩家，一個玩家能被這個觀察員觀察到當且僅當該玩家在第 W_j 秒也正好到達了節點 j。小C想知道每個觀察員會觀察到多少人？

注意：我們認為一個玩家到達自己的終點後，該玩家就會結束遊戲，他不能等待一段時間後再被觀察員觀察到。即對于把節點 j 作為終點的玩家：若他在第 W_j 秒前到達終點，則在節點 j 的觀察員不能觀察到該玩家；若他正好在第 W_j 秒到達終點，則在節點 j 的觀察員可以觀察到這個玩家。

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

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

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

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

對于所有的資料,保證 1<=Si,Ti<=N,0<=Wj<=N。

一行 N 個整數，第 i 個整數表示結點 i 的觀察員可以觀察到多少人。

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

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

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

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

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

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

CCF NOIP2016 D1T2

題解

分為兩段，可以分開做：

在\(S_i\)處産生\(d[S_i]\)，在\(fa[lca(S_i,T_i)]\)處減去它，在任意節點\(x\)處統計\(W[x]+d[x]\)的個數。

在\(T_i\)處産生\(d[S_i]-2*d[lca(S_i,T_i)]\)，在\(lca(S_i,T_i)\)處減去它，在任意節點\(x\)處統計\(W[x]-d[x]\)的個數。

而這個用不着線段樹合并，直接用在每個節點用vector存一下變動，開全局數組統計，用末值減去初值就是答案了。

時間複雜度\(O(m\log n+n)\)