boatherds?2s?64M?by czy

求一顆樹上距離為K的點對是否存在

輸入數據

n,m

接下來n-1條邊a,b,c描述a到b有一條長度為c的路徑

接下來m行每行詢問一個K

輸出數據

對于每個K每行輸出一個答案，存在輸出“AYE”,否則輸出”NYE”(不包含引號)

數據范圍

對于30%的數據n<=100

對于60%的數據n<=1000,m<=50

對于100%的數據n<=10000,m<=100,c<=1000,K<=10000000

---

?

點分治。

但是每次詢問會超時，所以需要離線。

就把K都存起來，每次詢問的時候都for一遍K。

代碼：

1 // #pragma comment(linker,"/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 9 const int N=10010; 10 int n,m,sl,kl,tl,vl,len,first[N],mark[N],s[N],t[N],d[N],size[N],K[N],ans[N];//,v[N]; 11 bool v[10000010]; 12 struct node{ 13 int x,y,d,next; 14 }a[2*N]; 15 16 bool cmp(int x,int y){return x<y;} 17 18 void ins(int x,int y,int d) 19 { 20 a[++len].x=x;a[len].y=y;a[len].d=d; 21 a[len].next=first[x];first[x]=len; 22 } 23 24 void find_root(int x,int fa,int tot,int &root) 25 { 26 size[x]=1; 27 bool bk=1; 28 for(int i=first[x];i;i=a[i].next) 29 { 30 int y=a[i].y; 31 if(y==fa || mark[y]) continue; 32 find_root(y,x,tot,root); 33 size[x]+=size[y]; 34 if(2*size[y]>tot) bk=0; 35 } 36 if(bk && 2*(tot-size[x])<=tot) root=x; 37 } 38 39 void DFS(int x,int fa) 40 { 41 for(int i=1;i<=kl;i++) 42 { 43 if(K[i]>=d[x] && v[K[i]-d[x]]) ans[i]=1; 44 } 45 // if(ans==1) return ; 46 t[++tl]=d[x]; 47 size[x]=1; 48 for(int i=first[x];i;i=a[i].next) 49 { 50 int y=a[i].y; 51 if(y==fa || mark[y]) continue; 52 d[y]=d[x]+a[i].d; 53 DFS(y,x); 54 size[x]+=size[y]; 55 } 56 } 57 58 void dfs(int x,int tot) 59 { 60 find_root(x,0,tot,x); 61 v[0]=1;sl=0;//ssl=0; 62 // s[++sl]=x; 63 mark[x]=1; 64 for(int i=first[x];i;i=a[i].next) 65 { 66 int y=a[i].y; 67 if(mark[y]) continue; 68 tl=0;d[y]=a[i].d; 69 DFS(y,x); 70 // if(ans==1) break; 71 for(int j=1;j<=tl;j++) v[t[j]]=1,s[++sl]=t[j]; 72 } 73 for(int i=1;i<=sl;i++) v[s[i]]=0; 74 // if(ans==1) return ; 75 for(int i=first[x];i;i=a[i].next) 76 { 77 int y=a[i].y; 78 if(mark[y]) continue; 79 dfs(y,size[y]); 80 } 81 } 82 83 int main() 84 { 85 // freopen("a.in","r",stdin); 86 freopen("boatherds.in","r",stdin); 87 freopen("boatherds.out","w",stdout); 88 scanf("%d%d",&n,&kl); 89 len=0; 90 memset(v,0,sizeof(v)); 91 memset(first,0,sizeof(first)); 92 for(int i=1;i<n;i++) 93 { 94 int x,y,c; 95 scanf("%d%d%d",&x,&y,&c); 96 ins(x,y,c); 97 ins(y,x,c); 98 } 99 for(int i=1;i<=kl;i++) scanf("%d",&K[i]); 100 memset(ans,0,sizeof(ans)); 101 dfs(1,n); 102 for(int i=1;i<=kl;i++) 103 { 104 if(ans[i]) printf("AYE\n"); 105 else printf("NAY\n"); 106 } 107 return 0; 108 }

?

轉載于:https://www.cnblogs.com/KonjakJuruo/p/6051259.html

總結

以上是生活随笔為你收集整理的【poj2114】点分治（离线）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。