Description

风见幽香非常喜欢玩一个叫做 osu!的游戏,其中她最喜欢玩的模式就是接水果。由于她已经DT FC 了The big black, 她觉得这个游戏太简单了,于是发明了一个更加难的版本。

首先有一个地图,是一棵由 $n$ 个顶点、$n-1$ 条边组成的树。

这颗树上有 $P$ 个盘子,每个盘子实际上是一条路径),并且每个盘子还有一个权值。第 $i$ 个盘子就是顶点$a_i$到顶点$b_i$的路径(由于是树,所以从$a_i$到$b_i$的路径是唯一的),权值为$c_i$。

接下来依次会有$Q$个水果掉下来,每个水果本质上也是一条路径,第i 个水果是从顶点 $u_i$ 到顶点$v_i$ 的路径。

幽香每次需要选择一个盘子去接当前的水果:一个盘子能接住一个水果,当且仅当盘子的路径是水果的路径的子路径.这里规定:从$a$ 到$b$的路径与从$b$到 $a$的路径是同一条路径。

当然为了提高难度,对于第 $i$ 个水果,你需要选择能接住它的所有盘子中,权值第 $k_i$ 小的那个盘子,每个盘子可重复使用(没有使用次数的上限:一个盘子接完一个水果后,后面还可继续接其他水果,只要它是水果路径的子路径)。幽香认为这个游戏很难,你能轻松解决给她看吗?

Input

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

Output

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

Solution

这题做法很多,用整体二分可以很方便地解决.不过莫队也是可以水的.

用树上莫队的套路排序好询问后,加入一个点时,考虑以这个点为端点的所有盘子,若另一个端点也在当前的链上,将其离散化后的权值加入线段树(树状数组,平衡树等支持第$k$大的均可),删除同理.注意以LCA为端点的盘子需要在询问时加入再删掉,然而这样有可能会破坏复杂度(事实上很难在看不到代码的情况下卡掉,因为DFS树根节点的选择也会影响LCA的位置).

这样我们就得到了一个时间复杂度$O(n^\frac{3}{2}logP + q logP)$的高(la)效(ji)算法.由于我在插入时使用的是树状数组(本意是想减小常数),询问时二分还多带了一个$log$.

Source

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define pb push_back

using namespace std;

const int N = 80010;

int n, m, q, sz;
vector<int> G[N];

struct Query{
	int l, r, lca, k, id;

	bool operator < (const Query& A) const{
		return l / sz == A.l / sz ? r < A.r : l < A.l;
	}
}A[N];

struct Plate{
	int to, val;
}B[N];

int Begin[N], Next[N], e;
void Add(int x, int y, int w){
	B[++e] = (Plate){y, w};
	Next[e] = Begin[x];
	Begin[x] = e;
}

int in[N], out[N], id[N], dfn;
int dep[N], fa[N][18];

void DFS(int h){
	in[h] = ++dfn, id[dfn] = h;
	For(i, 0, (int)G[h].size() - 1){
		int v = G[h][i];
		if(v == fa[h][0]) continue;
		fa[v][0] = h;
		For(j, 1, 17) fa[v][j] = fa[fa[v][j - 1]][j - 1];
		dep[v] = dep[h] + 1;
		DFS(v);
	}
	out[h] = ++dfn, id[dfn] = h;
}

int num[N], Ans[N], tot;

void findlca(Query& p){
	if(in[p.l] > in[p.r]) swap(p.l, p.r);
	int u = p.l, v = p.r;
	if(dep[u] < dep[v]) swap(u, v);
	int del = dep[u] - dep[v];
	Forr(i, 17, 0) if(del & (1 << i)) u = fa[u][i];
	if(u != v){
		Forr(i, 17, 0) if(fa[u][i] ^ fa[v][i]) u = fa[u][i], v = fa[v][i];
		p.lca = fa[u][0];
		p.l = out[p.l], p.r = in[p.r];
	}
	else p.l = in[p.l], p.r = in[p.r];
}

int c[N];

inline int lowbit(int x){
	return x & (-x);
}

inline void add(int x, int v){
	while(x <= n){
		c[x] += v;
		x += lowbit(x);
	}
}

inline int sum(int x){
	int ret = 0;
	while(x){
		ret += c[x];
		x -= lowbit(x);
	}
	return ret;
}

bool vis[N];

void change(int x){
	x = id[x];
	for(int i = Begin[x]; i; i = Next[i])
		if(vis[B[i].to]) add(B[i].val, vis[x] ? -1 : 1);
	vis[x] ^= 1;
}

int query(int k, int u){
	for(int i = Begin[u]; i; i = Next[i]) 
		if(vis[B[i].to]) add(B[i].val, 1);
	int L = 1, R = tot, M;
	while(L < R){
		M = (L + R) >> 1;
		if(sum(M) >= k) R = M;
		else L = M + 1;
	}
	for(int i = Begin[u]; i; i = Next[i]) 
		if(vis[B[i].to]) add(B[i].val, -1);
	return num[L];
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	For(i, 2, n){
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v), G[v].pb(u);
	}
	DFS(1);
	For(i, 1, m){
		int x, y, v;
		scanf("%d%d%d", &x, &y, &v);
		num[++tot] = v;
		Add(x, y, v), Add(y, x, v);
	}

	sort(num + 1, num + tot + 1);
	tot = (int)(unique(num + 1, num + tot + 1) - num) - 1;
	For(i, 1, e) B[i].val = (int)(lower_bound(num + 1, num + tot + 1, B[i].val) - num);

	For(i, 1, q) scanf("%d%d%d", &A[i].l, &A[i].r, &A[i].k), A[i].id = i, findlca(A[i]);
	sz = ceil(sqrt(2 * n));
	sort(A + 1, A + q + 1);

	int l = 0, r = 0;
	For(i, 1, q){
		while(r < A[i].r) change(++r);
		while(r > A[i].r) change(r--);
		while(l < A[i].l) change(l++);
		while(l > A[i].l) change(--l);
		Ans[A[i].id] = query(A[i].k, A[i].lca);
	}

	For(i, 1, q) printf("%d\n", Ans[i]);
	return 0;
}