点分治

淀粉质

可以处理一些有关树上路径的问题，先看题 8️⃣

P3806

首先对于一个点 $u$ 和它的子树中任意一个点 $v$ ， $dis(v)$ 表示 $v$ 到 $u$ 的路径权值和

考虑开一个桶 $u[k]$ 记录是否存在 $dis(v) = k$

那么不在同一个子树的两个点的贡献就好算了

对于一个存在的 $u[w],w <= k$ 如果存在 $u[k-w]$ 那么就存在这样一个点对

对于在同一个子树内点的贡献，我们把 $u$ 删去,把树拆开递归到这些子树中下去求解

肯定是拆成的子树大小越均衡越好，所以每次节点 $u$ 的选取要讲究一点

每次选取当前树的重心作为 $u$ ，总时间复杂度 $O(nlogn)$

Code

#include<bits/stdc++.h>
#define MAXN 10005
#define MAXK 10000005
#define ll long long
#define cjb 1145141919
using namespace std;
namespace F_star
{
    int cnte = 0, head[MAXN];
    struct edge
    {
        int to, nxt;
        ll dis;
    }e[MAXN << 1];
    void adde(int u, int v, ll w)
    {
        e[++cnte].to = v;
        e[cnte].dis = w;
        e[cnte].nxt = head[u];
        head[u] = cnte;
    }
}using namespace F_star;
struct query
{
    int k, ans;
}que[105];

int n,m;
int siz[MAXN];
int root, sixz, sum;
ll dis[MAXN];
bool vis[MAXN];
bool t[MAXK+5];

void get_zx(int u) //找重心
{
    int msiz = 0; // 不能定义成全局变量
    siz[u] = 1;
    vis[u] = true;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(vis[v]) continue;
        get_zx(v);
        siz[u] += siz[v];
        msiz = max(msiz, siz[v]);
    }
    msiz = max(msiz, sum - siz[u]);
    if(msiz < sixz) {sixz = msiz; root = u;}
    vis[u] = false;
}

ll sta1[MAXN], top1;
ll sta2[MAXN], top2;
int debug;
void get_dis(int u) //处理子树内个节点到当前根的路径权值
{
    if(dis[u] > MAXK) return;
    vis[u] = true;
    sta1[++top1] = dis[u];
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; if(vis[v]) continue;
        dis[v] = dis[u] + e[i].dis;
        get_dis(v);
    }
    vis[u] = false;
}
void get_ans(int u) //统计答案
{
    t[0] = 1;
    top2 = 0;
    vis[u] = true;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; if(vis[v]) continue;
        top1 = 0;
        dis[v] = e[i].dis; get_dis(v);

        for(int j = 1; j <= top1; j++)
        {
            for(int k = 1; k <= m; k++) //分别统计每个询问
            {
                if(sta1[j] <= que[k].k)
                que[k].ans |= t[que[k].k - sta1[j]];
            }
        }//先统计在加入贡献，保证统计的是不同子树的两点的贡献

        for(int j = 1; j <= top1; j++) 
        sta2[++top2] = sta1[j], t[sta1[j]] = 1; //加入子树贡献
    }
    for(int i = 1; i <= top2; i++) //清楚贡献
    t[sta2[i]] = 0;
    vis[u] = false;
}

void solve(int u) //分治函数
{
    get_ans(u);
    vis[u] = true;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(vis[v]) continue;
        sum = siz[v]; sixz = cjb;
        get_zx(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);
        adde(u, v, w); adde(v, u, w);
    }
    for(int i = 1; i <= m; i++)
    scanf("%d",&que[i].k);

    sum = n; sixz = cjb;
    get_zx(1);
    solve(root);
    for(int i = 1; i <= m; i++)
    printf(que[i].ans ? "AYE\n" : "NAY\n");

    return 0;
}