求助,关于淀粉质欸,悬赏若干关注(●'◡'●)

P3806 【模板】点分治 1

cjwdyzxfblzs @ 2023-06-07 19:46:11

在学淀粉质的时候先做了Tree这道题目,我看这道模板提就是改一下参数,把 \le 改成 = ,但是为什么会过不去呢。 (蒟蒻已经将修改的地方在代码里面标注出来了)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int p[N];
int q[N];
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
int get_size(int u, int fa)
{
    if (st[u])
        return 0;
    int res = 1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        res += get_size(j, u);
    }
    return res;
}
int get_wc(int u, int fa, int tot, int &wc)
{
    if (st[u])
        return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2)
        wc = u;
    return sum;
}
void get_dist(int u, int fa, int dist, int &qt)
{
    if (st[u])
        return;
    q[qt++] = dist;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        get_dist(j, u, dist + w[i], qt);
    }
}
int get(int a[], int k)
{
    sort(a, a + k);
    int res = 0;
    for (int i = k - 1, j = -1; i >= 0; i--)
    {
        while (j + 1 < i && a[j + 1] + a[i] == m) /* 这里把 小于等于 替换成了 等于 */
            j++;
        j = min(j, i - 1);
        res += j + 1;
    }
    return res;
}
int calc(int u)
{
    if (st[u])
        return 0;
    int res = 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt);
        for (int k = 0; k < qt; k++)
        {
            if (q[k] == m) /* 这里也是把 小于等于 替换成了 等于 */
                res++;
            p[pt++] = q[k];
        }
    }
    res += get(p, pt);
    for (int i = h[u]; i != -1; i = ne[i])
        res += calc(e[i]);
    return res;
}
int ak;
int main()
{
    cin >> n;
    cin >> ak;
    memset(h, -1, sizeof h);
    // memset(st, 0, sizeof st);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    while (ak--)
    {
        memset(st, false, sizeof(st));
        cin >> m;
        if (calc(2) || m == 0)
            cout << "AYE" << endl;
        else 
            cout << "NAY" << endl;
    }
    return 0;
}

by heaksicn @ 2023-06-07 19:50:51

@sjzez__chess 主函数里面是不是应该找重心在 calc


by cjwdyzxfblzs @ 2023-06-07 19:52:58

@heaksicn 我的重心在calc里面找的呀


by cjwdyzxfblzs @ 2023-06-07 19:53:41

@heaksicn 我这个是有什么问题吗???


by crimson000 @ 2023-06-07 19:54:13

小于等于满足单调性但是等于不满足单调性吧,所以不能用双指针应该


by cjwdyzxfblzs @ 2023-06-07 19:56:38

@crimson000 有道理欸


|