题目链接

洛谷P4178

洛谷P3806

题目分析

本题主要是点分治模板题,步骤如下:

  • dfs函数,用来找树的重心,注意需要进行两次,第一次以1为树根,找到树的重心,然后再以此重心为树根dfs一遍(因为树根不同时每个子树的大小是不同的)
  • divide分治,每次找到树的重心,然后求每个点到这个重心的距离,也就是getdis函数
  • solve函数主要是用来处理询问,每找到一个重心就进行一次solve函数,看看左右子树的各个距离有无满足条件的
  • 重点!!!如果要求距离恰好等于k,那么就用judge数组+queue
  • 重点!!!如果要求距离小于等于k,那么就用树状数组

题目代码

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
using namespace std;

const int N = 1e5 + 10;

int n, count1, sum, root, m, cnt, ans;
int dis[N], book[N], head[N], siz[N], mx[N], tmp[N], f[N];
struct node {
    int to, wei, nxt;
}e[N << 1];

void update(int pos) {
    for (int i = pos; i < N; i += lowbit(i))
        f[i]++;
}

int query(int pos) {
    int num = 0;
    for (int i = pos; i; i -= lowbit(i))
        num += f[i];
    return num;
}

void addedge(int u, int v, int wei) {
    e[++count1].to = v;
    e[count1].wei = wei;
    e[count1].nxt = head[u];
    head[u] = count1;
}

void dfs(int u, int pre) {
    siz[u] = 1;
    mx[u] = 0;
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v= e[i].to;
        if (v == pre || book[v]) continue;
        dfs(v, u);
        siz[u] += siz[v];
        mx[u] = max(mx[u], siz[v]);
    }
    mx[u] = max(mx[u], sum - siz[u]);
    if (mx[u] < mx[root]) root = u;
}

void getdis(int u, int pre) {
    if (dis[u] > m) return;
    tmp[++cnt] = dis[u];
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == pre || book[v]) continue;
        dis[v] = dis[u] + e[i].wei;
        getdis(v, u);
    }
}

void solve(int u) {
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (book[v]) continue;
        cnt = 0;
        dis[v] = e[i].wei;
        getdis(v, u);
        for (int j = 1; j <= cnt; j++) {
            if (tmp[j] <= m) ans++;  
            int res = query(m - tmp[j]);
            ans += res;
        }
        for (int j = 1; j <= cnt; j++)
            update(tmp[j]);
    }
    memset(f, 0, sizeof f);
}

void divide(int u) {
    book[u] = 1;
    solve(u);
    for (int i = head[u]; ~i; i =e[i].nxt) {
        int v = e[i].to;
        if (book[v]) continue;
        mx[root = 0] = sum = siz[v];
        dfs(v, 0);
        dfs(root, 0);
        divide(root);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%d", &n);
    memset(head, -1, sizeof head);
    for (int i = 1; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    scanf("%d", &m);
    mx[root = 0] = sum = n;
    dfs(1, 0);
    dfs(root, 0);
    divide(root);
    printf("%d", ans);

    return 0;
}

题目2代码

就是一个单纯的~淀粉汁~

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;
const int maxn = 1e7 + 10;
const int inf = 0x3f3f3f3f;

int n, m, count1, root, cnt, sum;
int book[N], mx[N], siz[N], head[N], tmp[N], dis[N], judge[maxn], ans[N], qr[N];
struct node {
    int to, wei, nxt;
}e[N << 1];

void addedge(int u, int v, int wei) {
    e[++count1].to = v;
    e[count1].wei = wei;
    e[count1].nxt = head[u];
    head[u] = count1;
}

void dfs(int u, int pre) {
    siz[u] = 1, mx[u] = 0;
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == pre || book[v]) continue;
        dfs(v, u);
        siz[u] += siz[v];
        mx[u] = max(mx[u], siz[v]);
    }
    mx[u] = max(mx[u], sum - siz[u]);
    if (mx[u] < mx[root]) {
        root = u;
    }
}

void getdis(int u, int pre) {
    if (dis[u] > maxn) return;
    tmp[++cnt] = dis[u];
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == pre || book[v]) continue;
        dis[v] = dis[u] + e[i].wei;
        getdis(v, u);
    }
}

void solve(int u) {
    queue<int> q;
    for (int i = head[u]; ~i; i =e[i].nxt) {
        int v = e[i].to;
        if (book[v]) continue;
        cnt = 0;
        dis[v] = e[i].wei;
        getdis(v, u);
        for (int j = 1; j <= cnt; j++) {
            for (int k = 1; k <= m; k++) {
                if (qr[k] >= tmp[j]) 
                    ans[k] |= judge[qr[k] - tmp[j]];
            }
        }
        for (int j = 1; j <= cnt; j++) {
            q.push(tmp[j]);
            judge[tmp[j]] = 1;
        }
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        judge[now] = 0;
    }
}

void divide(int u) {
    book[u] = judge[0] = 1;
    solve(u);
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (book[v]) continue;
        mx[root = 0] = sum = siz[v];
        dfs(v, 0);
        dfs(root, 0);
        divide(root);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof head);
    for (int i = 1; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    for (int i = 1; i <= m; i++) scanf("%d", &qr[i]);
    mx[root = 0] = sum = n; 
    dfs(1, 0);
    dfs(root, 0);
    divide(root);
    for (int i = 1; i <= m; i++) {
        printf("%s\n", (ans[i]) ? "AYE" : "NAY");
    }

    return 0;
}
最后修改:2021 年 04 月 02 日 10 : 00 PM