https://www.luogu.org/problem/show?pid=1600
小c同學認為跑步非常有趣,于是決定制作一款叫做《天天愛跑步》的遊戲。«天天愛跑步»是一個養成類遊戲,需要玩家每天按時上線,完成打卡任務。
這個遊戲的地圖可以看作一一棵包含
個結點和
條邊的樹, 每條邊連接配接兩個結點,且任意兩個結點存在一條路徑互相可達。樹上結點編号為從
到
的連續正整數。
現在有
個玩家,第
個玩家的起點為
,終點為
。每天打卡任務開始時,所有玩家在第
秒同時從自己的起點出發, 以每秒跑一條邊的速度, 不間斷地沿着最短路徑向着自己的終點跑去, 跑到終點後該玩家就算完成了打卡任務。 (由于地圖是一棵樹, 是以每個人的路徑是唯一的)
小C想知道遊戲的活躍度, 是以在每個結點上都放置了一個觀察員。 在結點
的觀察員會選擇在第
秒觀察玩家, 一個玩家能被這個觀察員觀察到當且僅當該玩家在第
秒也理到達了結點
。 小C想知道每個觀察員會觀察到多少人?
注意: 我們認為一個玩家到達自己的終點後該玩家就會結束遊戲, 他不能等待一 段時間後再被觀察員觀察到。 即對于把結點
作為終點的玩家: 若他在第
秒重到達終點,則在結點
的觀察員不能觀察到該玩家;若他正好在第
秒到達終點,則在結點
的觀察員可以觀察到這個玩家。
輸入格式：
第一行有兩個整數
和
。其中
代表樹的結點數量, 同時也是觀察員的數量,
代表玩家的數量。
接下來
行每行兩個整數
和
,表示結點
到結點
有一條邊。
接下來一行
個整數,其中第
個整數為
, 表示結點
出現觀察員的時間。
行,每行兩個整數
,和
,表示一個玩家的起點和終點。
對于所有的資料,保證
。
輸出格式：
輸出1行
個整數,第
個整數表示結點
的觀察員可以觀察到多少人。
輸入樣例#1：
輸出樣例#1：
輸入樣例#2：
輸出樣例#2：
測試點1——5：
數組a[i][j]表示點i在j時刻經過的人數，然後一個人一個人的dfs，記錄時刻time
如果到了終點，遞歸回退時a[now][time]++
令watch[i]=j表示i号節點觀察員在j時刻出現
輸出a[i][watch[i]]
測試點6——8：
樹退化為一條鍊，而且點的編号就是深度
是以對于鍊上一個觀察員，他隻能觀察到從兩個位置出發的人i+watch[i]，i-watch[i]
如果i能觀察到起點深度比他小的人，那麼這個人的終點要>=i
如果i能觀察到起點深度比他大的人，那麼這個人的終點要<=i
是以，
用連結清單存儲從每個節點起跑的人，
枚舉每個觀察員，然後判斷兩個位置的人是否滿足要求
測試點9——12：
所有人的起點都是1，假設1号的深度為0，
那麼隻有觀察員節點的深度等于出現時間，他才能觀察到
是以先判斷深度是否等于出現時間，不等，直接輸出0，下一個
若相等，他一定能觀察到經過他的所有人
也就是說，以觀察員i為根的子樹中有跑步者的終點，觀察員i就能觀察多少人
是以，終點+1，記錄每個節點的深度，我用的bfs，單後dfs統計子樹1的個數，
kids[]表示答案
測試點13——16：
所有人的終點都是1
也就是說，第i個觀察員隻能觀察到第deep[i]+watch[i]層的跑步者
是以，若跑步者能被觀察員i觀察到，要滿足以下兩個條件：
1、在起點觀察員i的子樹内
2、起點的層數=deep[i]+watch[i]
先對原樹dfs一遍，記錄觀察員i的子樹dfs序範圍in[i]——out[i]
對每一層維護一顆線段樹，動态開節點
查詢時，找到deep[i]+watch[i]這一層的線段樹，查in[i]——out[i]有多少個起點
所有暴力綜合代碼
作者：xxy
本文版權歸作者所有，轉載請用連結，請勿原文轉載，Thanks♪(･ω･)ﾉ。