BZOJ4151【AMPPZ2014】The Cave <树相关>

Problem

【AMPPZ2014】The Cave

Time Limit: $5 Sec$
Memory Limit: $256 MB$
$Special Judge$

Description

给定一棵有$n$个节点的树，相邻两点之间的距离为$1$。
请找到一个点$x$，使其满足所有$m$条限制 $a\ b\ d$，其中第$i$条限制为$dist_{x,a}+dist_{x,b}\le d$

Input

第一行包含一个正整数$t$($1\le t\le 1000$)，表示数据组数。
对于每组数据，第一行包含两个正整数$n,m$($2\le n,m\le 3\times 10^5$)，表示点数、限制数。
接下来$n-1$行，每行两个正整数$x,y$($1\le x,y\le n$)，表示树上的一条边。
接下来$m$行，每行三个正整数$a[i],b[i],d[i]$($1\le a[i],b[i]\le n$, $1\le d[i]\le 6\times 10^5$)，描述一条限制。
输入数据保证所有$n$之和不超过 $3\times 10^5$，所有$m$之和也不超过 $3\times 10^5$。

Output

输出$t$行。第$i$行输出第$i$组数据的答案，如果无解输出$NIE$，否则输出$TAK$，
然后输出$x$，如有多组解，输出任意一组。

Sample Input

2
5 3
1 2
2 3
2 4
3 5
1 4 2
5 5 5
3 2 1
3 2
1 2
2 3
1 1 2
3 3 1

Sample Output

TAK 2
NIE

标签：树相关

Solution

好题，完全没想到正解。
设$1$号节点为根节点。
对于每个限制，所求点离$a_i\to b_i$这条路径的距离一定不大于某个数，在根节点确定的情况下，第$i$个限制可转化成所求点到根的距离最大为$max(0,max_{i=1}^{n}{\frac{dep[a_i]+dep[b_i]−d_i}{2}})$以内，其中$dep$表示该点到根节点的距离。
这就可以转化成类似一堆已知某个端点的线段求某个交点的问题。
于是先取限制距离最大的线段上的点，即离根节点最远的点，然后一路往上跑直到某个点刚好满足限制，对于这个点再判断一下是否满足所有情况即可，总复杂度$O(n+m)$。
可参考另一篇写得很清楚的博客：小米狐的博客

Code

#include <bits/stdc++.h>
#define MAX_N 300000
using namespace std;
int n, m, a[MAX_N+5], b[MAX_N+5], d[MAX_N+5], pa[MAX_N+5], dep[MAX_N+5];
vector <int> G[MAX_N+5];
void DFS(int u, int fa) {
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];	if (v == fa)	continue;
        pa[v] = u, dep[v] = dep[u]+1, DFS(v, u);
    }
}
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);	for (int i = 1; i <= n; i++) G[i].clear();
        for (int i = 1, u, v; i < n; i++)	scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
        dep[1] = 0, DFS(1, 0);	int p = 1, mx = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d", a+i, b+i, d+i);
            if ((dep[a[i]]+dep[b[i]]-d[i]+1)/2 > mx)	p = a[i], mx = (dep[a[i]]+dep[b[i]]-d[i]+1)/2;
        }
        for (; dep[p] > mx; p = pa[p]) ;	dep[p] = 0, DFS(p, 0);	bool flag = true;
        for (int i = 1; i <= m; i++)	if (dep[a[i]]+dep[b[i]] > d[i]) {flag = false; break;}
        if (flag)	printf("TAK %d\n", p);	else	puts("NIE");
    }
    return 0;
}