询问树上距离为k的点对是否存在
直接n^2暴力处理点对 桶排记录 可以过
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], ed = 1; int cost[MAXM << 1]; int ok[10000005]; 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] = 1; f[x] = 0; 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 = 0; dep[x] = d; getdeep(x, 0); sort(o + 1, o + cnt + 1); for (int i = 1; i <= cnt; i++) { for (int j = i + 1; j <= cnt; j++) { ok[o[i] + o[j]] += add; } } } void solve(int x) { calc(x, 0, 1); vis[x] = 1; for (int i = Head[x]; i; i = nxt[i]) { int v = to[i]; if (vis[v]) { continue; } calc(v, cost[i], -1); root = 0, sumsz = sz[v]; getroot(v, 0); solve(root); } } int main() { scanf("%d %d", &n, &m); cnt = 0; memset(Head, 0, sizeof(Head)); memset(vis, 0, sizeof(vis)); memset(ok, 0, sizeof(ok)); ed = 1; int u, v, c; for (int i = 1; i < n; i++) { scanf("%d %d %d", &u, &v, &c); ADD(u, v, c); } root = 0, sumsz = f[0] = n; getroot(1, 0); solve(root); for (int i = 1; i <= m; i++) { scanf("%d", &k); if (ok[k]) { printf("AYE "); } else { printf("NAY "); } } return 0; }
用类似poj1741的方法:对于每一次询问 calc()函数中求出<=k的和>=k的数量再减去总对数 则为=k的数量
复杂度为O(m*n*log2n)
#include<bits/stdc++.h> #define MAXN 10005 #define INF 1e9+7 using namespace std; struct front_star{ int to,next,w; }edge[MAXN<<1]; int n,cnt=0,k,mx,root,ans=0,tot=1,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]=1; int msz=0; 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,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=n-1;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=1; idx[u]=1; temp[1]=val; dist(u,u); sort(temp+1,temp+1+tot); int L=1,R=tot,res1=0,res2=0,ret; while(L<=R) { if(temp[L]+temp[R]<=k) { res1+=R-L; L++; } else R--; } L=1,R=tot; while(L<=R) { if(temp[L]+temp[R]>=k) { res2+=R-L; R--; } else L++; } ret=res1+res2-(tot*(tot-1))/2; return ret; } void divide(int u) { ans+=count_ans(u,0); 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=1;i<=m;i++) { memset(vis,false,sizeof(vis)); scanf("%d",&k); siz=n; mx=INF; ans=0; findroot(1,1); divide(root); if(ans==0) printf("NAY "); else printf("AYE "); } } int main() { init(); query(); return 0; }