Description

眼看著假期就要到了，Crash由于長期切題而感到無聊了，因此他決定利用這個假期和好友陶陶一起出去旅游。
Crash和陶陶所要去的城市里有N (N > 1) 個景點，Crash用正整數1到N給景點標號。
這些景點之間通過N - 1條無向道路相連，每條道路有一個長度，并且保證任意兩個景點之間都有且僅有一條路徑相連。
現在對于一個景點s，Crash和陶陶從s出發，然后訪問一個景點序列{v0, v1, v2, … , vk}，
其中v0就是s，且vi-1和vi(0 < i ≤ k)之間有道路相連。
需要注意的是，陶陶和Crash訪問的景點序列中不會只有景點s。
為了使旅程不顯得乏味，在一個景點序列里他們不會重復走某條道路。
我們定義這個序列的旅游代價為經過道路的長度和。下面問題出現了：
陶陶：我們走一條景點數最多的景點序列吧。
Crash：倒，你想把我累死啊。
陶陶：誰叫你整天坐在電腦前面，不出來鍛煉，這下子傻了吧，哈哈哈哈~~
Crash：不行，如果你非要走景點數最多的我就不陪你走了。
陶陶：笑噴油你很跳嘛！
Crash：這樣吧，我們來寫伸展樹，如果我寫的比你快，你就要聽我的。
陶陶：這樣不公平哎，我們來玩PES吧，當然你要讓我選法國隊，如果你輸了你就要聽我的。
Crash：倒，你這是欺負我，T_T~
陶陶：笑噴油好說話哎。
Crash：囧……
……
這樣搞了半天，最終陶陶和Crash用很多次包剪錘決定出選擇旅游代價第K小 的景點序列。
不過呢Crash和陶陶還沒確定開始旅行的景點s，因此他希望你對于每個景點i，計算從景點i開始的景點序列中旅游代價第K小的值。

Input

共N行。
第1行包含一個字符和兩個正整數，字符為ABCD中的一個，用來表示這個測試數據的類型
（詳見下面的數據規模和約定），另外兩個正整數分別表示N和K (K < N),N<=100000
第2行至第N行，每行有三個正整數u、v和w (u, v ≤ N，w ≤ 10000)。
表示u號景點和v號景點之間有一條道路，長度為w。
輸入文件保證符合題目的約定，即任意兩個景點之間都有且僅有一條路徑相連。

Output

共N行，每行有一個正整數。
第i行的正整數表示從i號景點開始的景點序列中旅游代價第K小的代價。

Sample Input

A 6 3

1 2 2

1 3 4

1 4 3

3 5 1

3 6 2

Sample Output

4

6

4

7

5

6

//樣例1中輸出對應的景點序列分別為：

1號景點是{1, 3}，2號景點是{2, 1, 3}，3號景點是{3, 1}，4號景點是{4, 1, 3}，5號景點是{5, 3, 1}，6號景點是{6, 3, 1}。

保證每個景點到1號景點需要經過的道路數不超過30

---

題解

題意就是給出\(n\)個點的一棵樹,對于每個點求出距離ta第\(k\)小的距離

動態點分治
我們可以先建出點分樹
然后二分一個距離\(k\),判斷其他點到這個點的距離小于等于這個值的有幾個
那么現在的問題就是給出一個點,求出到這個點的距離不大于\(k\)的有幾個點
記\(v1[u]\)數組表示\(u\)的子樹內的點到\(u\)的距離,\(v2[u]\)表示\(u\)的子樹內的點到\(fa[u]\)的距離
然后每次查詢點\(u\)的時候就順著點分樹往上跳,期間查詢所有的點到點\(u\)的距離不超過\(k\)的點
注意每次往上跳到\(fa[u]\)再查\(fa[u]\)的子樹的時候會把已經統計過的\(u\)的子樹的信息重復統計一部分,所以我們要容斥掉\(u\)的子樹內的信息
注意往上跳的時候如果跳到點\(x\)使得\(dis(u,x)>k\)也不要直接\(break\),而是要繼續往上跳,因為點分樹是將原樹重構了,可能\(dis(u,x)>k\)了但是\(x\)的祖先到\(u\)的距離\(\le k\)

代碼

#include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> const int M = 200005 ; const int INF = 1e9 ; using namespace std ;inline int read() {char c = getchar() ; int x = 0 , w = 1 ;while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }return x*w ; }bool vis[M] ; int n , k , num , tot , tmx , root , hea[M] ; int dis[M] , ff[M] , fa[M] , size[M] , dep[M] , son[M] , top[M] ; vector < int > v1[M] , v2[M] ; struct E { int nxt , to , dis ; } edge[M * 2] ; inline void add_edge(int from , int to , int dis) {edge[++num].nxt = hea[from] ; edge[num].to = to ;edge[num].dis = dis ; hea[from] = num ; }void dfs1(int u , int father , int depth) {ff[u] = father ; size[u] = 1 ; dep[u] = depth ; int mx = -1 ;for(int i = hea[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(v == father) continue ;dis[v] = dis[u] + edge[i].dis ; dfs1(v , u , depth + 1) ; size[u] += size[v] ; if(size[v] > mx) mx = size[v] , son[u] = v ;} } void dfs2(int u , int topf) {top[u] = topf ; if(!son[u]) return ; dfs2(son[u] , topf) ;for(int i = hea[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(v == ff[u] || v == son[u]) continue ;dfs2(v , v) ;} } inline int LCA(int x , int y) {while(top[x] != top[y]) {if(dep[top[x]] < dep[top[y]]) swap(x , y) ;x = ff[top[x]] ;}return dep[x] < dep[y] ? x : y ; } inline int Gdis(int x , int y) {return dis[x] + dis[y] - dis[LCA(x , y)] * 2 ; } void findroot(int u , int father) {size[u] = 1 ; int mx = 0 ;for(int i = hea[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(vis[v] || v == father) continue ;findroot(v , u) ; mx = max(mx , size[v]) ; size[u] += size[v] ;}mx = max(mx , tot - size[u]) ;if(mx < tmx) tmx = mx , root = u ; }void Solve(int u , int father) {fa[u] = father ; vis[u] = true ;for(int i = hea[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(vis[v]) continue ;tot = size[v] ; tmx = INF ; findroot(v , u) ; Solve(root , u) ;} } // v1 表示u的子樹內的點到u的距離 // v2 表示u的子樹內的點到fa[u]的距離 inline void Insert(int x) {v1[x].push_back(0) ;for(int u = x ; fa[u] ; u = fa[u]) {v1[fa[u]].push_back(Gdis(x , fa[u])) ;v2[u].push_back(Gdis(x , fa[u])) ;} } inline int query(int id , int x , int k) {if(id == 1) {int l = 0 , r = v1[x].size() - 1 , mid , ret = -1 ;while(l <= r) {mid = (l + r) >> 1 ;if(v1[x][mid] <= k) l = mid + 1 , ret = mid ;else r = mid - 1 ;}return ret + 1 ;}else {int l = 0 , r = v2[x].size() - 1 , mid , ret = -1 ;while(l <= r) {mid = (l + r) >> 1 ;if(v2[x][mid] <= k) l = mid + 1 , ret = mid ;else r = mid - 1 ;}return ret + 1 ;} } inline int check(int x , int k) {int ans = query(1 , x , k) ;for(int u = x , dis1 ; fa[u] ; u = fa[u]) {dis1 = Gdis(x , fa[u]) ; if(k - dis1 < 0) continue ;ans += query(1 , fa[u] , k - dis1) - query(2 , u , k - dis1) ;}return ans - 1 ; } int main() {char s[10] ; scanf("%s",s) ; n = read() ; k = read() ;for(int i = 1 , u , v , w ; i < n ; i ++) {u = read() ; v = read() ; w = read() ;add_edge(u , v , w) ; add_edge(v , u , w) ;}dfs1(1 , 0 , 1) ; dfs2(1 , 1) ; tot = n ; tmx = INF ; findroot(1 , 0) ; Solve(root , 0) ;for(int i = 1 ; i <= n ; i ++) Insert(i) ;for(int i = 1 ; i <= n ; i ++) {sort(v1[i].begin() , v1[i].end()) ;sort(v2[i].begin() , v2[i].end()) ;}for(int u = 1 ; u <= n ; u ++) {int l = 1 , r = 1e9 , ret = 0 ;while(l <= r) {int mid = (l + r) >> 1 ;if(check(u , mid) >= k) ret = mid , r = mid - 1 ;else l = mid + 1 ;}printf("%d\n",ret) ;}return 0 ; }

轉載于:https://www.cnblogs.com/beretty/p/10645671.html

總結

以上是生活随笔為你收集整理的[2010国家集训队]Crash的旅游计划的全部內容，希望文章能夠幫你解決所遇到的問題。

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