点分治

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <set>
  8 #include <map>
  9 #include <queue>
 10 #include <iostream>
 11 using namespace std;
 12 
 13 #define ll long long
 14 
 15 const int maxn=1e4+10;
 16 const int maxq=1e2+10;
 17 const int maxvalue=1e7+10;
 18 const int inf=1e9;
 19 const double eps=1e-8;
 20 
 21 /*
 22 找重心
 23 子树再找重心
 24 根，子树(s) 间的操作
 25 可能要除去单个子树内两个结点的重复
 26 */
 27 
 28 struct node
 29 {
 30     int d,len;
 31     node *to;
 32 }*e[maxn];
 33 
 34 ll sum[maxq];   ///in case
 35 int query[maxq],siz[maxn],q,nn;
 36 int curroot,mins,clrvis[maxn],clrdist[maxn];
 37 int exist[maxvalue];
 38 bool has[maxn],vis[maxn];
 39 
 40 void dfs(int d)
 41 {
 42     int dd,maxsiz=0;
 43     siz[d]=1;
 44     clrvis[++clrvis[0]]=d;
 45     vis[d]=1;
 46     node *p=e[d];
 47     while (p)
 48     {
 49         dd=p->d;
 50         if (!vis[dd] && !has[dd])
 51         {
 52             dfs(dd);
 53             maxsiz=max(maxsiz,siz[dd]);
 54             siz[d]+=siz[dd];
 55         }
 56         p=p->to;
 57     }
 58     maxsiz=max(maxsiz,nn-siz[d]);
 59     if (maxsiz<mins)
 60         mins=maxsiz,curroot=d;
 61 }
 62 
 63 void finddist(int d,int dis)
 64 {
 65     int dd;
 66     clrvis[++clrvis[0]]=d;
 67     vis[d]=1;
 68     clrdist[++clrdist[0]]=dis;
 69     node *p=e[d];
 70     while (p)
 71     {
 72         dd=p->d;
 73         if (!vis[dd] && !has[dd])
 74             finddist(dd,dis+p->len);
 75         p=p->to;
 76     }
 77 }
 78 
 79 void work(int d)
 80 {
 81     int root,dd,i,j,preind,firind;
 82     firind=clrdist[0];
 83     mins=inf;   ///10000 * 10000
 84     nn=siz[d],dfs(d);
 85     for (i=1;i<=clrvis[0];i++)
 86         vis[clrvis[i]]=0;
 87     clrvis[0]=0;
 88     root=curroot;
 89     has[root]=1;
 90     if (d!=root)
 91         siz[d]=nn-siz[root];    ///
 92 
 93     node *p=e[root];
 94     while (p)
 95     {
 96         dd=p->d;
 97         if (!has[dd])
 98         {
 99             work(dd);
100             preind=clrdist[0];
101             finddist(dd,p->len);
102             for (i=1;i<=clrvis[0];i++)
103                 vis[clrvis[i]]=0;
104             clrvis[0]=0;
105 
106             for (i=preind+1;i<=clrdist[0];i++)
107                 exist[clrdist[i]]++;
108 
109             for (i=preind+1;i<=clrdist[0];i++)
110                 for (j=1;j<=q;j++)
111                     if (query[j]>clrdist[i])
112                         sum[j]-=exist[clrdist[i]]*exist[query[j]-clrdist[i]];
113 
114             for (i=preind+1;i<=clrdist[0];i++)
115                 exist[clrdist[i]]--;
116 
117         }
118         p=p->to;
119     }
120 
121     for (i=firind+1;i<=clrdist[0];i++)
122         exist[clrdist[i]]++;
123 
124     for (i=firind+1;i<=clrdist[0];i++)
125         for (j=1;j<=q;j++)
126             if (query[j]>=clrdist[i])
127                 sum[j]+=exist[clrdist[i]]*exist[query[j]-clrdist[i]];
128     ///这里多算了
129     ///v+v=query[i] -exist[v]
130     ///相同的只要计算一次exist[v](重复多次)*exist[query[i]-v]
131     ///exist[p]*exist[q] exist[q]*exist[p] 重复
132 
133     for (i=firind+1;i<=clrdist[0];i++)
134         exist[clrdist[i]]--;
135     clrdist[0]=firind;
136 
137     has[root]=0;    ///取消不能走的限制
138 }
139 
140 int main()
141 {
142     node *p;
143     int n,i,a,b,c;
144     scanf("%d%d",&n,&q);
145     for (i=1;i<n;i++)
146     {
147         scanf("%d%d%d",&a,&b,&c);
148         p=new node();
149         p->d=b;
150         p->len=c;
151         p->to=e[a];
152         e[a]=p;
153 
154         p=new node();
155         p->d=a;
156         p->len=c;
157         p->to=e[b];
158         e[b]=p;
159     }
160     for (i=1;i<=q;i++)
161         scanf("%d",&query[i]);
162 
163     exist[0]=1;
164     siz[1]=n,work(1);
165 
166     for (i=1;i<=q;i++)
167         if (sum[i]==0)
168             printf("NAY\n");
169         else
170             printf("AYE\n");
171     return 0;
172 }
173 /*
174 6 15
175 1 2 2
176 1 3 3
177 2 6 3
178 3 4 1
179 3 5 2
180 1
181 2
182 3
183 4
184 5
185 6
186 7
187 8
188 9
189 10
190 11
191 12
192 13
193 14
194 15
195 
196 6 15
197 1 2 1
198 1 3 3
199 1 4 4
200 1 5 7
201 5 6 1
202 1
203 2
204 3
205 4
206 5
207 6
208 7
209 8
210 9
211 10
212 11
213 12
214 13
215 14
216 15
217 */