BZOJ4151【AMPPZ2014】The Cave <树相关>

Problem

【AMPPZ2014】The Cave

Time Limit:
Memory Limit:

Description

给定一棵有个节点的树，相邻两点之间的距离为。
请找到一个点，使其满足所有条限制，其中第条限制为

Input

第一行包含一个正整数()，表示数据组数。
对于每组数据，第一行包含两个正整数()，表示点数、限制数。
接下来行，每行两个正整数()，表示树上的一条边。
接下来行，每行三个正整数(, )，描述一条限制。
输入数据保证所有之和不超过，所有之和也不超过。

Output

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

Sample Input

Sample Output

1
2

TAK 2
NIE

标签：树相关

Solution

好题，完全没想到正解。
设号节点为根节点。
对于每个限制，所求点离这条路径的距离一定不大于某个数，在根节点确定的情况下，第个限制可转化成所求点到根的距离最大为以内，其中表示该点到根节点的距离。
这就可以转化成类似一堆已知某个端点的线段求某个交点的问题。
于是先取限制距离最大的线段上的点，即离根节点最远的点，然后一路往上跑直到某个点刚好满足限制，对于这个点再判断一下是否满足所有情况即可，总复杂度。
可参考另一篇写得很清楚的博客：小米狐的博客

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;
}