【题面】
求一颗树上距离为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
【思路】
树分治。
离线存储m个询问。分治判断该m个询问是否能够出现。
具体操作：假设当前处理第S个子树，exist[]中存储着前S-1棵子树中出现过的dis，一遍dfs得到S子树的所有dis，并判断m个询问。
时间复杂度为O(nmlogn)
别放了exist[0] <- 0和清空exist就好了QAQ
【代码】
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int N = 1e4+;
const int M = 1e7+; struct Edge {
int v,w;
Edge(int v=,int w=) :v(v),w(w){}
};
vector<Edge> g[N];
int n,m,k,q[N],ans[N];
int root,size,siz[N],f[N],dis[N],vis[N],tmp[N],l1,l2,exist[M]; void getroot(int u,int fa) {
siz[u]=; f[u]=; exist[]=;
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(v!=fa && !vis[v]) {
getroot(v,u);
siz[u]+=siz[v];
if(siz[v]>f[u]) f[u]=siz[v];
}
}
f[u]=max(f[u],size-siz[u]);
if(f[u]<f[root]) root=u;
}
void dfs(int u,int fa) {
tmp[++l1]=dis[u];
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(v!=fa && !vis[v]) {
dis[v]=dis[u]+g[u][i].w;
dfs(v,u);
}
}
}
void solve(int u) {
vis[u]=;
l1=l2=;
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
l2=l1+;
if(!vis[v]) {
dis[v]=g[u][i].w;
dfs(v,u);
FOR(i,l2,l1) FOR(j,,m)
if(q[j]>=tmp[i] && exist[q[j]-tmp[i]]) ans[j]=;
FOR(i,l2,l1) exist[tmp[i]]=;
}
}
FOR(i,,l1) exist[tmp[i]]=;
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(!vis[v]) {
root=; getroot(u,-);
size=siz[v]; solve(root);
}
}
} void read(int& x) {
char c=getchar(); int f=; x=;
while(!isdigit(c)){if(c=='-') c=-; c=getchar();}
while(isdigit(c)) x=x*+c-'',c=getchar();
x*=f;
}
int main() {
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
read(n),read(m);
int u,v,w;
FOR(i,,n-) {
read(u),read(v),read(w);
g[u].push_back(Edge(v,w));
g[v].push_back(Edge(u,w));
}
FOR(i,,m) read(q[i]);
size=n; f[]=1e9; root=;
getroot(,-); solve(root);
FOR(i,,m) if(ans[i]) puts("AYE"); else puts("NAY");
return ;
}