询问树上距离为k的点对是否存在

直接n^2暴力处理点对 桶排记录 可以过

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + ;
const int MAXM = 1e5 + ;
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], ed = ;
int cost[MAXM << ];
int ok[];
inline void addedge(int u, int v, int c) {
to[++ed] = v;
cost[ed] = c;
nxt[ed] = Head[u];
Head[u] = ed;
}
inline void ADD(int u, int v, int c) {
addedge(u, v, c);
addedge(v, u, c);
}
int n, m, k;
int sz[MAXN], f[MAXN], dep[MAXN], sumsz, root;
bool vis[MAXN];
int o[MAXN], cnt;
void getroot(int x, int fa) {
sz[x] = ;
f[x] = ;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa || vis[v]) {
continue;
}
getroot(v, x);
sz[x] += sz[v];
f[x] = max(f[x], sz[v]);
}
f[x] = max(f[x], sumsz - sz[x]);
if (f[x] < f[root]) {
root = x;
}
}
void getdeep(int x, int fa) {
o[++cnt] = dep[x];
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa || vis[v]) {
continue;
}
dep[v] = dep[x] + cost[i];
getdeep(v, x);
}
}
void calc(int x, int d, int add) {
cnt = ;
dep[x] = d;
getdeep(x, );
sort(o + , o + cnt + );
for (int i = ; i <= cnt; i++) {
for (int j = i + ; j <= cnt; j++) {
ok[o[i] + o[j]] += add;
}
}
}
void solve(int x) {
calc(x, , );
vis[x] = ;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) {
continue;
}
calc(v, cost[i], -);
root = , sumsz = sz[v];
getroot(v, );
solve(root);
}
}
int main() {
scanf("%d %d", &n, &m);
cnt = ;
memset(Head, , sizeof(Head));
memset(vis, , sizeof(vis));
memset(ok, , sizeof(ok));
ed = ;
int u, v, c;
for (int i = ; i < n; i++) {
scanf("%d %d %d", &u, &v, &c);
ADD(u, v, c);
}
root = , sumsz = f[] = n;
getroot(, );
solve(root);
for (int i = ; i <= m; i++) {
scanf("%d", &k);
if (ok[k]) {
printf("AYE\n");
} else {
printf("NAY\n");
}
}
return ;
}

用类似poj1741的方法:对于每一次询问 calc()函数中求出<=k的和>=k的数量再减去总对数 则为=k的数量

复杂度为O(m*n*logn)

#include<bits/stdc++.h>
#define MAXN 10005
#define INF 1e9+7
using namespace std;
struct front_star{
int to,next,w;
}edge[MAXN<<];
int n,cnt=,k,mx,root,ans=,tot=,siz,m;
int head[MAXN],sz[MAXN],temp[MAXN],idx[MAXN];
bool vis[MAXN];
int maxn(int a,int b)
{
return a>b?a:b;
}
void addedge(int u,int v,int c)
{
cnt++;
edge[cnt].to=v;
edge[cnt].w=c;
edge[cnt].next=head[u];
head[u]=cnt;
}
void findroot(int u,int fa)
{
sz[u]=;
int msz=;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(v!=fa&&!vis[v])
{
findroot(v,u);
sz[u]+=sz[v];
msz=maxn(msz,sz[v]);
}
}
msz=maxn(msz,siz-sz[u]);
if(msz<mx)
{
mx=msz;
root=u;
}
}
void init()
{
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<=n-;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
}
void dist(int u,int fa)
{
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v]&&v!=fa)
{
tot++;
idx[v]=tot;
temp[tot]=temp[idx[u]]+edge[i].w;
dist(v,u);
}
}
}
int count_ans(int u,int val)
{
tot=;
idx[u]=;
temp[]=val;
dist(u,u);
sort(temp+,temp++tot);
int L=,R=tot,res1=,res2=,ret;
while(L<=R)
{
if(temp[L]+temp[R]<=k)
{
res1+=R-L;
L++;
}
else
R--;
}
L=,R=tot;
while(L<=R)
{
if(temp[L]+temp[R]>=k)
{
res2+=R-L;
R--;
}
else
L++;
}
ret=res1+res2-(tot*(tot-))/;
return ret;
}
void divide(int u)
{
ans+=count_ans(u,);
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v]&&!vis[v])
{
ans-=count_ans(v,edge[i].w);
siz=sz[v];
mx=INF;
findroot(v,u);
divide(root);
}
}
}
void query()
{
for(int i=;i<=m;i++)
{
memset(vis,false,sizeof(vis));
scanf("%d",&k);
siz=n;
mx=INF;
ans=;
findroot(,);
divide(root);
if(ans==)
printf("NAY\n");
else
printf("AYE\n");
}
}
int main()
{
init();
query();
return ;
}
05-11 17:28