问题有三:
1、~~y=e[p].to~~ y=e[i].to
2、应该在计算dis(ask函数)时更新以当前重心为根的子树的size
3、询问离线,点分治常熟过大,会导致tle
by SSpider_Man @ 2023-10-18 14:50:50
@[lovely_Rex](/user/704234)
by SSpider_Man @ 2023-10-18 14:51:20
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxv=1e7+5;
struct edge{
int to,val;
};
int n,m,root,size[maxn],Bigchildsize,opt[maxn],ans[maxn],p,q[maxn];
bool vis[maxn];
int d[maxv];
vector<edge> e[maxn];
void findroot(int u,int fa,int tot){
size[u]=1;
int mxsize=0;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].to;
if(vis[v] || v==fa) continue;
findroot(v,u,tot);
mxsize=max(mxsize,size[v]);
size[u]+=size[v];
}
mxsize=max(mxsize,tot-size[u]);
if(mxsize<Bigchildsize){
Bigchildsize=mxsize;
root=u;
}
}
void Getdis(int u,int fa,int dis){
if(dis<=1e7) opt[++p]=dis;
size[u]=1;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].to;
if(vis[v] || v==fa) continue;
Getdis(v,u,dis+e[u][i].val);
size[u]+=size[v];
}
}
void calc(int l,int r){
for(int i=l;i<=r;i++){
for(int j=1;j<=m;j++){
if(q[j]>=opt[i])
ans[j]+=d[q[j]-opt[i]];
}
}
for(int i=l;i<=r;i++)
d[opt[i]]++;
}
void dec(){
for(int i=1;i<=p;i++)
d[opt[i]]--;
}
void solve(int u,int fa,int tot){
root=u;
Bigchildsize=tot;
findroot(u,fa,tot);
p=0;
d[0]=1;
opt[++p]=0;
vis[root]=1;
for(int i=0;i<e[root].size();i++){
int v=e[root][i].to;
if(vis[v]) continue;
int pre=p;
Getdis(v,root,e[root][i].val);
calc(pre+1,p);
}
dec();
int rt=root;
for(int i=0;i<e[rt].size();i++){
int v=e[rt][i].to;
if(vis[v]) continue;
// cout<<v<<" "<<rt<<" "<<size[v]<<"\n";
solve(v,rt,size[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].push_back((edge){v,w});
e[v].push_back((edge){u,w});
}
for(int i=1;i<=m;i++)
scanf("%d",&q[i]);
solve(1,0,n);
for(int i=1;i<=m;i++){
if(ans[i]) printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
```
by SSpider_Man @ 2023-10-18 14:55:11
第三部没做,所以T了
by SSpider_Man @ 2023-10-18 14:55:51