题目描述

给出一棵n个点的树,给定m条路径,每条路径有一个权值。q次询问求一个路径包含的所有给定路径中权值第k小的。

输入

第一行三个数 n和P 和Q,表示树的大小和盘子的个数和水果的个数。

接下来n-1 行,每行两个数 a、b,表示树上的a和b 之间有一条边。树中顶点
按1到 n标号。 接下来 P 行,每行三个数 a、b、c,表示路径为 a 到 b、权值为 c 的盘子,其
中0≤c≤10^9,a不等于b。 
接下来Q行,每行三个数 u、v、k,表示路径为 u到 v的水果,其中 u不等于v,你需要选择第 k小的盘子,
第k小一定存在。 

输出

对于每个果子,输出一行表示选择的盘子的权值。

样例输入

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序+树上倍增+整体二分+树状数组

咦这不是 Highways 那道题吗?只不过是变成一条路径包含的给定路径,求第k小。

那么按照那道题的方法,要求的就是包含询问点(包含其它路径的路径,询问路径)的给定矩形(被包含的路径,给定路径)中权值第k小的。

可以想到整体二分,统计一个点在多少个权值在$[l,mid]$范围内的矩形中出现过。可以使用离线+树状数组解决。

时间复杂度$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;
}

最新文章

  1. js获取页面url中的各项值
  2. Unity3D 游戏前端开发技能树(思维导图)
  3. 前端优秀作品展示,JavaScript 版水果忍者
  4. git曲线
  5. uva 10755 - Garbage Heap
  6. jQuery-对Radio/CheckBox的操作集合
  7. iOS 除去图片的白色背景(接近白色),或者其它颜色的替换,获取像素点的ARGB值
  8. jQuery iframe 自适应高宽度
  9. css 中 的 float :left 和 clear :both
  10. Cylinder
  11. JavaScript学习笔记(高级部分—02)
  12. c++(数据选择)
  13. Python爬虫实战之Requests+正则表达式爬取猫眼电影Top100
  14. JAVA执行远端服务器的脚本
  15. Ubuntu脚本修改IP信息
  16. KO的使用例子
  17. PHP-问题处理Fatal error: Uncaught Error: Call to undefined function mb_strlen()
  18. 【转】Oracle virtual column(虚拟列)
  19. A+B (带有,的数字)
  20. 11.14java课堂测试

热门文章

  1. oracle中connect by语句的优化
  2. cent os 上安装 matlab
  3. 使用zxing二维码识别
  4. 新知识 HtMl 5
  5. 23种java设计模式之装饰者模式及动态代理
  6. Spring笔记1
  7. C errno是否是线程安全的
  8. Python2 Sequence类型簇
  9. 7 tftp
  10. 1698-Just a Hook 线段树(区间替换)