9.11
闲话
做题纪要
9.12
闲话
做题纪要
luogu P3806 【模板】点分治 1
-
若边权都为 \(1\) ，求出直径后判断即可。
-
点分治板子。
- 随意选择一个点作为根节点 \(rt\) ，则所以完全位于当前其子树内的路径以是否经过 \(rt\) 分为两种。而经过 \(rt\) 的路径 \(u \to v(u,v \ne rt)\) 又可以拆分成 \(u \to rt,rt \to v\) 两条路径。
- 考虑分治，对于枚举的 \(rt\) ，先计算在其子树内且经过 \(rt\) 的路径对答案产生的贡献，然后递归其子树对不经过该节点的路径进行求解。
- 点分治过程中，每一层的所有递归过程对每个点处理一次，时间复杂度为 \(O(hn)\) ，其中 \(h\) 为树高/递归层数。
- 若每次选择子树的中心作为根节点，可以保证递归层数最少，时间复杂度为 \(O(n \log n)\) 。
- 视询问情况决定是否让时间复杂度多乘上一个 \(O(m)\) 。
- 在重新选择根节点后一定要重新计算子树的大小。
-
对于经过根节点 \(rt\) 的路径，先计算出 \(x\) 子树内节点 \(x\) 到根节点的距离 \(dis_{x}\) ， \(judge_{d}\) 表示之前处理的子树中是否存在长度为 \(d\) 的路径。若一个询问的 \(k\) 满足 \(judge_{k-dis_{x}}=1\) 则说明存在一条长度为 \(k\) 的路径。处理完一棵子树的询问后及时更新 \(judge\) 。
-
清空 \(judge\) 数组时必须手动清空，否则使用
memset清空会导致时间复杂度错误。- 具体地，将占用过的 \(judge\) 的位置加入一个队列里，然后进行清空。
-
时间复杂度为 \(O(nm \log n)\) ，空间复杂度为 \(O(V)\) 。
- 由于 \(k \le 10^{7}\) ， \(judge\) 和队列中只保存 \(\le 10^{7}\) 的数，剩下的数一定不可能对答案产生贡献。
点击查看代码
struct node { int nxt,to,w; }e[20010]; int head[20010],ask[20010],ans[20010],cnt=0; void add(int u,int v,int w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } struct Divide_On_Tree { int siz[20010],weight[20010],vis[20010],dis[20010],tmp[20010],judge[10000010],center; queue<int>q; void init(int n,int m) { center=0; get_center(1,0,n);//求重心 get_siz(center,0);//更新大小（单独写一个函数来减小常数） divide(center,0,m); } void get_center(int x,int fa,int n) { siz[x]=1; weight[x]=0; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa&&vis[e[i].to]==0) { get_center(e[i].to,x,n); siz[x]+=siz[e[i].to]; weight[x]=max(weight[x],siz[e[i].to]); } } weight[x]=max(weight[x],n-siz[x]); if(weight[x]<=n/2) { center=x; } } void get_siz(int x,int fa) { siz[x]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa&&vis[e[i].to]==0) { get_siz(e[i].to,x); siz[x]+=siz[e[i].to]; } } } void get_dis(int x,int fa) { tmp[0]++;//方便便利整颗子树的所有节点的 dis tmp[tmp[0]]=dis[x]; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa&&vis[e[i].to]==0) { dis[e[i].to]=dis[x]+e[i].w; get_dis(e[i].to,x); } } } void divide(int x,int fa,int m) { judge[0]=1; q.push(0); vis[x]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa&&vis[e[i].to]==0)//因为有了重心的参与单纯判断父亲节点不再可做 { tmp[0]=0; dis[e[i].to]=e[i].w; get_dis(e[i].to,x); for(int j=1;j<=tmp[0];j++) { for(int k=1;k<=m;k++) { if(ask[k]>=tmp[j]) { ans[k]|=judge[ask[k]-tmp[j]]; } } } for(int j=1;j<=tmp[0];j++) { if(tmp[j]<=10000000) { q.push(tmp[j]); judge[tmp[j]]=1; } } } } while(q.empty()==0) { judge[q.front()]=0; q.pop(); } for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa&&vis[e[i].to]==0) { center=0; get_center(e[i].to,x,siz[e[i].to]); get_siz(center,0); divide(center,x,m); } } } }T; int main() { int n,m,u,v,w,i; cin>>n>>m; for(i=1;i<=n-1;i++) { cin>>u>>v>>w; add(u,v,w); add(v,u,w); } for(i=1;i<=m;i++) { cin>>ask[i]; } T.init(n,m); for(i=1;i<=m;i++) { if(ans[i]==1) { cout<<"AYE"<<endl; } else { cout<<"NAY"<<endl; } } return 0; }