[AMPPZ2014]Jaskinia

题目大意：

一个\(n(n\le3\times10^5)\)的树，\(m(m\le3\times10^5)\)个约束条件\((a_i,b_i,d_i)\)。请你找到一个点\(x\)，满足\(dist(x,a_i)+dist(x,b_i)\le d_i\)。

思路：

对于每个条件，找出尽可能靠近根的合法点\(e_i\)，然后在所有\(e_i\)中找到最深的那个，判断是否合法。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=3e5+1;

int a[N],b[N],d[N],par[N],dep[N];

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

	e[v].push_back(u);

}

void dfs(const int &x,const int &par) {

	::par[x]=par;

	dep[x]=dep[par]+1;

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs(y,x);

	}

}

inline int jump(int x,const int &t) {

	while(dep[x]>t) x=par[x];

	return x;

}

int main () {

	for(register int T=getint();T;T--) {

		const int n=getint(),m=getint();

		for(register int i=1;i<n;i++) {

			add_edge(getint(),getint());

		}

		dfs(1,0);

		int low=1,id=0;

		for(register int i=1;i<=m;i++) {

			a[i]=getint(),b[i]=getint(),d[i]=getint();

			const int t=std::max((dep[a[i]]+dep[b[i]]-d[i]+1)/2,1);

			if(t>=low) {

				low=t;

				id=i;

			}

		}

		const int ans=jump(a[id],low);

		dfs(ans,0);

		for(register int i=1;i<=m;i++) {

			if(dep[a[i]]+dep[b[i]]-2>d[i]) goto Fail;

		}

		printf("TAK %d\n",ans);

		goto Succ;

		Fail:

			puts("NIE");

		Succ:

			for(register int i=1;i<=n;i++) {

				e[i].clear();

			}

	}

	return 0;

}