題目描述

給出一棵n個(gè)點(diǎn)的樹，給定m條路徑，每條路徑有一個(gè)權(quán)值。q次詢問求一個(gè)路徑包含的所有給定路徑中權(quán)值第k小的。

輸入

第一行三個(gè)數(shù) n和P 和Q，表示樹的大小和盤子的個(gè)數(shù)和水果的個(gè)數(shù)。?

接下來n-1 行，每行兩個(gè)數(shù) a、b，表示樹上的a和b 之間有一條邊。樹中頂點(diǎn) 按1到 n標(biāo)號(hào)。 接下來 P 行，每行三個(gè)數(shù) a、b、c，表示路徑為 a 到 b、權(quán)值為 c 的盤子，其 中0≤c≤10^9，a不等于b。? 接下來Q行，每行三個(gè)數(shù) u、v、k，表示路徑為 u到 v的水果，其中 u不等于v，你需要選擇第 k小的盤子， 第k小一定存在。?

輸出

對(duì)于每個(gè)果子，輸出一行表示選擇的盤子的權(quán)值。?

樣例輸入

10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 2 217394434
10 7 13022269
6 7 283254485
6 8 333042360
4 6 442139372
8 3 225045590
10 4 922205209
10 8 808296330
9 2 486331361
4 9 551176338
1 8 5
3 8 3
3 8 4
1 8 3
4 8 1
2 3 1
2 3 1
2 3 1
2 4 1
1 4 1

樣例輸出

442139372
333042360
442139372
283254485
283254485
217394434
217394434
217394434
217394434
217394434

---

題解

DFS序+樹上倍增+整體二分+樹狀數(shù)組

咦這不是 Highways 那道題嗎？只不過是變成一條路徑包含的給定路徑，求第k小。

那么按照那道題的方法，要求的就是包含詢問點(diǎn)（包含其它路徑的路徑，詢問路徑）的給定矩形（被包含的路徑，給定路徑）中權(quán)值第k小的。

可以想到整體二分，統(tǒng)計(jì)一個(gè)點(diǎn)在多少個(gè)權(quán)值在$[l,mid]$范圍內(nèi)的矩形中出現(xiàn)過。可以使用離線+樹狀數(shù)組解決。

時(shí)間復(fù)雜度$O(n\log^2n)$

然而我的代碼完全不可讀。。。就別看了。。。

#include <cstdio> #include <algorithm> #define N 40010 using namespace std; struct data {int x , y , z , v , w;data() {}data(int a , int b , int c , int d , int e) {x = a , y = b , z = c , v = d , w = e;}bool operator<(const data &a)const {return x < a.x;} }a[N * 3] , q[N * 2] , t[N * 2]; int n , head[N] , to[N << 1] , next[N << 1] , cnt , fa[N][20] , deep[N] , log[N] , pos[N] , last[N] , tp , tot , f[N] , val[N] , cc[N] , ans[N]; bool cmp(const data &a , const data &b) {return a.v < b.v; } inline void add(int x , int y) {to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt; } void dfs(int x) {int i;pos[x] = ++tp;for(i = 1 ; (1 << i) <= deep[x] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1];for(i = head[x] ; i ; i = next[i])if(to[i] != fa[x][0])fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i]);last[x] = tp; } int find(int x , int y) {int i;for(i = log[y] ; ~i ; i -- )if((1 << i) <= y)x = fa[x][i] , y -= (1 << i);return x; } inline void update(int x , int a) {int i;for(i = x ; i <= n ; i += i & -i) f[i] += a; } inline int query(int x) {int i , ans = 0;for(i = x ; i ; i -= i & -i) ans += f[i];return ans; } void solve(int b , int e , int l , int r , int L , int R) {if(b > e) return;int i;if(L == R){for(i = b ; i <= e ; i ++ ) ans[q[i].z] = L;return;}int MID = (L + R) >> 1 , mid = l - 1 , p = l;for(i = b ; i <= e ; i ++ ) cc[q[i].z] = 0;sort(a + l , a + r + 1 , cmp);while(mid < r && a[mid + 1].v <= MID) mid ++ ;sort(a + l , a + mid + 1);for(i = b ; i <= e ; i ++ ){while(p <= mid && a[p].x <= q[i].x) update(a[p].y , a[p].w) , update(a[p].z + 1 , -a[p].w) , p ++ ;cc[q[i].z] += query(q[i].y);}while(p > l) p -- , update(a[p].y , -a[p].w) , update(a[p].z + 1 , a[p].w);for(p = i = b ; i <= e ; i ++ ) if(val[q[i].z] <= cc[q[i].z]) t[p ++ ] = q[i];for(p = i = e ; i >= b ; i -- ) if(val[q[i].z] > cc[q[i].z]) t[p -- ] = q[i];for(i = b ; i <= e ; i ++ ){if(~cc[q[i].z] && val[q[i].z] > cc[q[i].z]) val[q[i].z] -= cc[q[i].z] , cc[q[i].z] = -1;q[i] = t[i];}solve(b , p , l , mid , L , MID) , solve(p + 1 , e , mid + 1 , r , MID + 1 , R); } int main() {int m , k , i , x , y , z , t;scanf("%d%d%d" , &n , &m , &k);for(i = 2 ; i <= n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x) , log[i] = log[i >> 1] + 1;dfs(1);for(i = 1 ; i <= m ; i ++ ){scanf("%d%d%d" , &x , &y , &z);if(deep[x] > deep[y]) swap(x , y);if(deep[x] < deep[y] && fa[t = find(y , deep[y] - deep[x] - 1)][0] == x){a[++tot] = data(1 , pos[y] , last[y] , z , 1);a[++tot] = data(pos[t] , pos[y] , last[y] , z , -1);a[++tot] = data(last[t] + 1 , pos[y] , last[y] , z , 1);}else a[++tot] = data(pos[x] , pos[y] , last[y] , z , 1) , a[++tot] = data(last[x] + 1 , pos[y] , last[y] , z , -1);}for(i = 1 ; i <= k ; i ++ ) scanf("%d%d%d" , &x , &y , &val[i]) , q[i] = data(pos[x] , pos[y] , i , 0 , 0) , q[i + k] = data(pos[y] , pos[x] , i , 0 , 0);sort(q + 1 , q + k * 2 + 1) , solve(1 , k * 2 , 1 , tot , 1 , 1000000000);for(i = 1 ; i <= k ; i ++ ) printf("%d\n" , ans[i]);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7725576.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj4009】[HNOI2015]接水果 DFS序+树上倍增+整体二分+树状数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。