[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;
}
05-11 20:28