Sad_Rex @ 2023-07-24 14:04:47
#include<bits/stdc++.h>
//#pragma GCC optimize(3, "Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
#define int long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
int vis=1,ans=0;
char x=getchar();
while(x<'0'||x>'9'){
if(x=='-')vis=-1;
x=getchar();
}
while(x>='0'&&x<='9'){
ans=ans*10+x-'0';
x=getchar();
}
return vis*ans;
}
inline void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
int n=read(),m=read();
const int N=1e4+9,M=1e8+9;
int u,v,w;
int minn=LONG_LONG_MAX;
struct node{
int nxt,to,w;
}e[2*N];
int head[N],cnt;
inline void add(int x,int y,int w){
++cnt;
e[cnt].to=y;
e[cnt].nxt=head[x];
e[cnt].w=w;
head[x]=cnt;
}
int root,size[N],maxnson[N];
bool vis[N];
int tmp=0,dis[N];
int Sumnode;
int num[M];
inline void get_heavy(int p,int fa){
size[p]=1,maxnson[p]=0;
for(int i=head[p];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]||y==fa)continue;
get_heavy(y,p);
size[p]+=size[y];
maxnson[p]=max(maxnson[p],size[y]);
}
maxnson[p]=max(maxnson[p],Sumnode-size[p]);
if(maxnson[p]<minn)minn=maxnson[p],root=p;
}
inline void ask(int begin,int fa,int len){
dis[++tmp]=len;
for(int i=head[begin];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]||y==fa)continue;
ask(y,begin,len+e[i].w);
}
}
inline void init(int p,int len,bool f){
tmp=0;
ask(p,0,len);
if(f==1){
for(int i=1;i<tmp;i++){
for(int j=i+1;j<=tmp;j++){
num[dis[i]+dis[j]]++;
}
}
}else if(f==0){
for(int i=1;i<tmp;i++){
for(int j=i+1;j<=tmp;j++){
num[dis[i]+dis[j]]--;
}
}
}
}
inline void difen(int p){
vis[p]=1;
init(p,0,1);
for(int i=head[p];i;i=e[i].nxt){
int y=e[p].to;
if(vis[y])continue;
init(y,e[i].w,0);
minn=LONG_LONG_MAX,root=0,Sumnode=size[y];
get_heavy(y,0);
difen(root);
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen("SB.out","w",stdout);
Sumnode=n;
for(int i=1;i<n;i++){
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
get_heavy(1,0);
difen(root);
while(m--){
int k=read();
if(num[k])puts("AYE");
else puts("NAY");
}
return 0;
}
/*
2 1
1 2 2
2
*/by SSpider_Man @ 2023-10-18 14:50:50
问题有三：
1、y=e[p].to y=e[i].to
2、应该在计算dis(ask函数)时更新以当前重心为根的子树的size
3、询问离线，点分治常熟过大,会导致tle
by SSpider_Man @ 2023-10-18 14:51:20
@lovely_Rex
by SSpider_Man @ 2023-10-18 14:55:11
#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:51
第三部没做，所以T了