算法学习
看这里
但他的代码中有一些错误
一个是在计算前没有先计算子树大小，另一个是没有在修改 \(ex\) 函数时判断是否越界（ex是我的函数）
建议看我的代码的注释(P3806 )
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,K=1e7+5,inf=1e9+5;
struct edge{int v,w;
};
vector<edge>b[N];
vector<int>query,del;
int n,root,mn,tot,m;
int dis[N],dp[N],vis[N],siz[N],ans[N];
bool ex[K];
void getsiz(int x,int f){siz[x]=1;for(auto i:b[x]){if(vis[i.v]||i.v==f) continue;getsiz(i.v,x);siz[x]+=siz[i.v];}
}
void getroot(int x,int f,int sum){siz[x]=1;dp[x]=0;for(auto i:b[x]){if(vis[i.v]||i.v==f) continue;getroot(i.v,x,sum);siz[x]+=siz[i.v];dp[x]=max(dp[x],siz[i.v]);}dp[x]=max(dp[x],sum-siz[x]);if(dp[x]<mn) root=x,mn=dp[x];
}
void getdis(int x,int w,int f){dis[++tot]=w;for(auto i:b[x]){if(vis[i.v]||i.v==f) continue;getdis(i.v,w+i.w,x);}
}
void figue(int x){for(auto i:b[x]){if(vis[i.v]) continue;tot=0;getdis(i.v,i.w,x);//每一个子树单独枚举,并且深度已经是w了,并且从i.v开始调用,记得改fafor(int j=1;j<=tot;j++){int cnt=0;for(int k=0;k<query.size();k++){if(query[k]>=dis[j]) ans[k]|=ex[query[k]-dis[j]];//先判断防止越界} }for(int j=1;j<=tot;j++){if(dis[j]<K) ex[dis[j]]=1,del.push_back(dis[j]);//防止越界}}for(int k:del) ex[k]=0;del.clear();
}
void solve(int x){ex[0]=1;//路径正好经过rootvis[x]=1;figue(x);for(auto i:b[x]){if(vis[i.v]) continue;//加了一个vis的判断mn=inf;getsiz(i.v,x);//因为之前并不知道子树的大小，所以要提前计算getroot(i.v,x,siz[i.v]);//传当前子树大小solve(root);}
}
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);b[u].push_back({v,w});b[v].push_back({u,w});}for(int i=1;i<=m;i++){int k;scanf("%d",&k);query.push_back(k);}mn=inf;getroot(1,0,n);solve(root);for(int i=0;i<m;i++){if(ans[i]) printf("AYE\n");else printf("NAY\n");}
}
T1:
trick:
判断一个序列中两个数的加和有多少小于k，可以枚举每一个数，然后判断有多少数小于它与k的差，树状数组维护即可
或者是二分？但这道题是动态的，我怕二分会炸
注这道题洛谷原题w是可以等于0的，所以要用支持修改0的树状数组
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5,inf=1e9+5,K=2e4+5;
struct edge{int v,w;
};
vector<edge>b[N];
vector<int>del;
int n,root,mn,tot,k,ans;
int dis[N],dp[N],vis[N],siz[N],tr[K];
int lowbit(int x){return x&(-x);
}
void add(int x,int z){if(x==0){//可能为0tr[0]+=z;return;}for(;x<K;x+=lowbit(x)){tr[x]+=z;}
}
int ask(int x){int res=0;for(;x;x-=lowbit(x)){res+=tr[x];}return res+tr[0];
}
void getsiz(int x,int f){siz[x]=1;for(auto i:b[x]){if(vis[i.v]||i.v==f) continue;getsiz(i.v,x);siz[x]+=siz[i.v];}
}
void getroot(int x,int f,int sum){siz[x]=1;dp[x]=0;for(auto i:b[x]){if(vis[i.v]||i.v==f) continue;getroot(i.v,x,sum);siz[x]+=siz[i.v];dp[x]=max(dp[x],siz[i.v]);}dp[x]=max(dp[x],sum-siz[x]);if(dp[x]<mn) root=x,mn=dp[x];
}
void getdis(int x,int w,int f){dis[++tot]=w;for(auto i:b[x]){if(vis[i.v]||i.v==f) continue;getdis(i.v,w+i.w,x);}
}
void figue(int x){// printf("root=%d\n",x);for(auto i:b[x]){if(vis[i.v]) continue;tot=0;getdis(i.v,i.w,x);//每一个子树单独枚举,并且深度已经是w了,并且从i.v开始调用,记得改fafor(int j=1;j<=tot;j++){if(k>=dis[j]) ans+=ask(k-dis[j]);}for(int j=1;j<=tot;j++){// printf("%d %d\n",dis[j],k);if(dis[j]<=k){// printf("%d ",dis[j]);ans++;//计算以重心为终点的贡献add(dis[j],1);del.push_back(dis[j]);} }// printf("\n");}for(int j:del) add(j,-1);del.clear();
}
void solve(int x){vis[x]=1;figue(x);for(auto i:b[x]){if(vis[i.v]) continue;//加了一个vis的判断mn=inf;getsiz(i.v,x);//因为之前并不知道子树的大小，所以要提前计算getroot(i.v,x,siz[i.v]);//传当前子树大小solve(root);}
}
int main(){scanf("%d",&n);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);b[u].push_back({v,w});b[v].push_back({u,w});}scanf("%d",&k);mn=inf;getroot(1,0,n);solve(root);printf("%d",ans);
}