点分治T飞求助

P3806 【模板】点分治 1

meizhuhe @ 2022-10-03 14:54:27

Rt,苟弱刚刚开始学习点分治,于是照着自己的理解去敲模板题,结果T飞,只得到了 30pts ,并确定不是死循环所导致,TLE #4 #6 #7 #9,实在是找不出原因,望诸位能给予帮助,感激不尽。

#include <bits/stdc++.h>
#define MAXN 10009
#define MAXM 109
using namespace std;
int n,m,root,ans;
int k;
int head[MAXN],nxt[MAXN<<1],to[MAXN<<1],wt[MAXN<<1],cnt;
int tsz[MAXN],arv[MAXN];
int reach[MAXN],tot;
bool vis[MAXN];
const int inf=0x7f7f7f7f;
inline void match(int u,int v,int w){
    ++cnt;
    nxt[cnt]=head[u];
    to[cnt]=v;
    wt[cnt]=w;
    head[u]=cnt;
}
inline void read(int& x){
    x=0;
    register char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
void getroot(int u,int f,int Tsize){
    tsz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v]||v==f)
            continue;
        getroot(v,u,Tsize);
        tsz[u]+=tsz[v];
        arv[u]=max(arv[u],tsz[v]);
    }
    arv[u]=max(arv[u],Tsize-tsz[u]);
    if(arv[u]<arv[root])
        root=u;
}
void getdis(int u,int f,int d){
    reach[tot++]=d;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v]||v==f)
            continue;
        getdis(v,u,d+wt[i]);
    }
}
int calc(int u,int d){
    int res=0;
    tot=0;
    getdis(u,0,d);
    sort(reach,reach+tot);
    for(int pl=0,pr=tot-1;pl<tot;++pl){
        while(pr>=0&&reach[pl]+reach[pr]>k)
            --pr;
        while(pr>=0&&reach[pl]+reach[pr]==k)
            --pr,++res;
    }
    return res;
}
void dfs(int u){
    vis[u]=1;
    ans+=calc(u,0);
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])
            continue;
        ans-=calc(v,wt[i]);
        root=0;
        getroot(v,0,tsz[v]);
        dfs(root);
    }
}
void init(){
    ans=0;
    getroot(1,0,n);
    memset(vis,0,sizeof(vis));
    memset(tsz,0,sizeof(tsz));
}
int main(){
    read(n);read(m);
    for(int i=1;i<n;i++){
        int u,v,w;
        read(u);read(v);read(w);
        match(u,v,w);
        match(v,u,w);
    }
    arv[0]=inf;
    for(int i=1;i<=m;i++){
        scanf("%d",&k);
        init();
        dfs(root);
        printf("%s\n",ans?"AYE":"NAY");
    }
    return 0;
}
/*
6 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
5
*/

|