题解 | #武#

输入的是一个树的结构，她的家在 $PP$ 点，就以 $PP$ 为根，dfs 求出每个点到 $PP$ 的距离 $\text{dis}\backslash text\{dis\}$，然后以 $\text{dis}\backslash text\{dis\}$ 来排序，找到离她家第 $KK$ 远的点即可。

求距离的时候可以用到公式：（假如 $uu$ 是一个结点，$vv$ 是 $uu$ 的孩子结点）

$\text{dis}(v)=\text{dis}(u)+value\backslash text\{dis\}(v)=\backslash text\{dis\}(u)+value$，其中 $valuevalue$ 是 $u\leftrightarrow vu\backslash leftrightarrow\; v$ 之间的距离。

#include<cstdio>
#include<vector>
#include<algorithm>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e5 + 5;
std::vector<int> G[N], G2[N];
int dis[N];
void dfs(int u, int fa) {
    int len = G[u].size();
    for (int i = 0; i < len; ++i) {
        int v = G[u][i];
        if (v == fa) continue;
        dis[v] = dis[u] + G2[u][i];
        dfs(v, u);
    }
}
int a[N];
bool cmp(int x, int y){
    return dis[x] < dis[y];
}
int main(){
    int n = init(), p = init(), k = init();
    for (int i = 1; i < n; ++i) {
        int u = init(), v = init(), w = init();
        G[u].push_back(v), G[v].push_back(u);
        G2[u].push_back(w), G2[v].push_back(w);
    }
    dfs(p, p);
    for (int i = 1; i <= n; ++i)
        if (i != p) a[++a[0]] = i;
    std::stable_sort(a + 1, a + 1 + a[0], cmp);
    print(dis[a[k]]), putchar('\n');
}