更新日志

2025/01/07：开工。

概念

点分治，通常用于处理大规模的树上路径信息问题。

思路

我们将原问题划分为多种，对于每个节点，统计经过这个节点且位于这棵子树内的路径答案。

为了缩减复杂度，对于每一棵子树，我们都找到它的重心，以重心为新根在子树内进行操作。

找重心示例：

int cnt,sz[N];//当前处理的部分总节点数，当前节点内节点数
void getsiz(int now,int fid){
    sz[now]=1;cnt++;
    for(auto e:vs[now]){
        int nxt=e.fir;
        if(nxt!=fid&&!ok[nxt]){
            getsiz(nxt,now);
            sz[now]+=sz[nxt];
        }
    }
}

int rot;//重心
int f[N];//最大子树大小
void getrot(int now,int fid){
    f[now]=cnt-sz[now];
    for(auto e:vs[now]){
        int nxt=e.fir;
        if(nxt!=fid&&!ok[nxt]){
            getrot(nxt,now);
            chmax(f[now],sz[nxt]);
        }
    }
    if(f[now]<f[rot])rot=now;
}

void calc(int rt){
    cnt=0;getsiz(rt,rt);//获取大小
    rot=0;f[0]=inf;getrot(rt,rt);//获取重心
    /*一些操作*/
}

（重心就是最大子树大小最小的。）

通常情况下，我们有需要去清空一些数组。为了保证复杂度正确，我们把修改过的点存到队列里，最后清空时一个一个取出归零。

更新完一个节点后，其每一棵子树都是独立的，分别递归即可。注意判断那个节点是否已经作为重心被操作过。

例题

点分治

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;

const int N=1e4+5,M=105,K=1e7+5;

int n,m;
vec<pil> vs[N];

int ask[M];bool ans[M];

bool ok[N];

int cnt,sz[N];
void getsiz(int now,int fid){
    sz[now]=1;cnt++;
    for(auto e:vs[now]){
        int nxt=e.fir;
        if(nxt!=fid&&!ok[nxt]){
            getsiz(nxt,now);
            sz[now]+=sz[nxt];
        }
    }
}

int rot;
int f[N];
void getrot(int now,int fid){
    f[now]=cnt-sz[now];
    for(auto e:vs[now]){
        int nxt=e.fir;
        if(nxt!=fid&&!ok[nxt]){
            getrot(nxt,now);
            chmax(f[now],sz[nxt]);
        }
    }
    if(f[now]<f[rot])rot=now;
}

bool st[K];
int que[N],top;
void getdis(int now,int fid,int dis){
    if(dis>=K)return;
    que[++top]=dis;
    for(auto e:vs[now]){
        int nxt=e.fir,val=e.sec;
        if(nxt!=fid&&!ok[nxt]){
            getdis(nxt,now,dis+val);
        }
    }
}

void calc(int rt){
    cnt=0;getsiz(rt,rt);
    rot=0;f[0]=inf;getrot(rt,rt);
    top=0;que[++top]=0;st[0]=1;
    for(auto e:vs[rot]){
        int nxt=e.fir,val=e.sec;
        if(ok[nxt])continue;
        int i=top;getdis(nxt,rot,val);
        rep(q,1,m)if(!ans[q]){
            rep(j,i+1,top){
                if(ask[q]>=que[j]&&st[ask[q]-que[j]]){
                    ans[q]=1;
                    break;
                }
            }
        }
        rep(j,i+1,top)st[que[j]]=1;
    }
    while(top)st[que[top--]]=0;
    ok[rot]=1;
    for(auto e:vs[rot]){
        int nxt=e.fir;
        if(!ok[nxt])calc(nxt);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    rep(i,2,n){
        int a,b,c;cin>>a>>b>>c;
        vs[a].pub({b,c});
        vs[b].pub({a,c});
    }
    rep(i,1,m)cin>>ask[i];
    calc(1);
    rep(i,1,m)cout<<(ans[i]?"AYE\n":"NAY\n");
    return 0;
}