题目背景
感谢hzwer的点分治互测。
题目描述
给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入输出格式
输入格式：
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式：
对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)
输入输出样例
说明
对于30%的数据n<=100
对于60%的数据n<=1000,m<=50
对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000
比较常规的一道点分治【然而我又因为一些奇奇怪怪的错误调了半天】
先以重心为根，对每个子树dfs统计到根的路径长度，将这些长度丢进hash表里【偷懒的我用了STL】，对于每个子树，在丢进去之前，查询之前子树是否存在路径 = K - d，存在则OK
之后往子树重心分治
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
using namespace std;
const int maxn = 10005,maxm = 10000005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int n,m,h[maxn],ne = 0,F[maxn],Siz[maxn],rt = 0,sum,vis[maxn];
int d[maxn],id[maxn],K,cnt;
bool flag;
map<int,int> H;
struct EDGE{int to,nxt,w;}ed[maxm];
inline void build(int u,int v,int w){
ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++;
ed[ne] = (EDGE){u,h[v],w}; h[v] = ne++;
}
void getRT(int u,int f){
int to; F[u] = 0; Siz[u] = 1;
Redge(u) if ((to = ed[k].to) != f && !vis[to]){
getRT(to,u); F[u] = max(F[u],Siz[to]); Siz[u] += Siz[to];
}
F[u] = max(F[u],sum - Siz[u]);
if (F[u] < F[rt]) rt = u;
}
void dfs(int u,int f){
int to; id[++cnt] = u;
Redge(u) if ((to = ed[k].to) != f && !vis[to]){
d[to] = d[u] + ed[k].w;
dfs(to,u);
}
}
void solve(int u){
vis[u] = true; int to;
H.clear(); H[0]++;
Redge(u) if (!vis[to = ed[k].to]){
d[to] = ed[k].w; cnt = 0; dfs(to,u);
REP(i,cnt) if (H.count(K - d[id[i]])) {flag = true;return;}
REP(i,cnt) H[d[id[i]]]++;
}
Redge(u) if (!vis[to = ed[k].to]){
sum = Siz[to]; F[rt = 0] = INF;
getRT(to,u); solve(rt);
if (flag) return;
}
}
int main(){
memset(h,-1,sizeof(h));
n = RD(); m = RD(); int a,b,w;
REP(i,n - 1) a = RD(),b = RD(),w = RD(),build(a,b,w);
while (m--){
memset(vis,false,sizeof(vis));
K = RD(); flag = false;
F[rt = 0] = INF; sum = n; getRT(1,0);
solve(rt);
if (flag) printf("AYE
");
else printf("NAY
");
}
return 0;
}