你说得对,但是我是最后一个点 Wa

P1600 [NOIP2016 提高组] 天天爱跑步

Phrvth @ 2023-07-26 23:02:36

不知道Lca有没有问题,着重看吧

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + 7, Siz = 3e4 + 7;

int n, m, W[MAXN], S[MAXN], T[MAXN];

struct Node {
    int nxt, to;
}Edge1[2 * MAXN], Edge2[2 * MAXN], Edge3[2 * MAXN];

int H1[MAXN], H2[MAXN], H3[MAXN], E1, E2, E3;

void add1(int from , int to) {
    Edge1[++ E1] = Node {H1[from], to};
    H1[from] = E1;
}
void add2(int from , int to) {
    Edge2[++ E2] = Node {H2[from], to};
    H2[from] = E2;
}
void add3(int from , int to) {
    Edge3[++ E3] = Node {H3[from], to};
    H3[from] = E3;
}

int Dep[MAXN], F[MAXN][30]; 

void dfs1(int u, int fa) {
    Dep[u] = Dep[fa] + 1; F[u][0] = fa;
    for (int i = 1; i <= log2(Dep[u]); i ++)
        F[u][i] = F[F[u][i - 1]][i - 1];
    for (int i = H1[u]; i; i = Edge1[i].nxt) {
        int v = Edge1[i].to; 
        if (v == fa) continue;
        dfs1(v, u);
    }
}

int Lca(int x, int y) {
    if (Dep[x] < Dep[y]) swap(x, y);
    while (Dep[x] > Dep[y]) x = F[x][(int)log2(Dep[x] - Dep[y])];
    if (x == y) return x;
    for (int i = log2(Dep[x]); i >= 0; i --) 
        if (F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
    return F[x][0];
}

int T1[2 * MAXN], T2[2 * MAXN], V[MAXN], Dis[MAXN], Ans[MAXN];

/*
对于每个节点 s,它作为起点的代价是固定的,即为多少个点作为起点
但它作为终点的代价并不是固定的,每条路径以 s 为终点的代价都是不一样的
lca也一样

有两点,答案为差值,和 lca 往上的点都没用
最后判下当链的起点就为 lca 的情况,减掉即可
*/

void dfs2(int u) {
    int t1 = T1[W[u] + Dep[u]], t2 = T2[W[u] - Dep[u] + Siz];
    for (int i = H1[u]; i; i = Edge1[i].nxt) {
        int v = Edge1[i].to;
        if (v == F[u][0]) continue;
        dfs2(v);
    }
    T1[Dep[u]] += V[u];//起点的贡献
    for (int i = H2[u]; i; i = Edge2[i].nxt) {
        int v = Edge2[i].to;//注意,这里的v为边的编号
        T2[Dis[v] - Dep[T[v]] + Siz] ++;//终点的贡献
    }
    Ans[u] += T1[W[u] + Dep[u]] - t1 + T2[W[u] - Dep[u] + Siz] - t2;
    for (int i = H3[u]; i; i = Edge3[i].nxt) {
        int v = Edge3[i].to;
        T1[Dep[S[v]]] --; T2[Dis[v] - Dep[T[v]] + Siz] --;
    }
}

int main () {
    cin >> n >> m;
    for (int i = 1, u, v; i < n; i ++) {
        cin >> u >> v; add1(u, v); add1(v, u);
    }
    dfs1(1, 0);
    for (int i = 1; i <= n; i ++) cin >> W[i];
    for (int i = 1; i <= m; i ++) {
        cin >> S[i] >> T[i];
        int lca = Lca(S[i], T[i]);
        Dis[i] = Dep[S[i]] + Dep[T[i]] - 2 * Dep[lca]; V[S[i]] ++;
        add2(T[i], i); add3(lca, i);
        if (Dep[lca] + W[lca] == Dep[S[i]]) Ans[lca] --;
    }
    dfs2(1);
    for (int i = 1; i <= n; i ++) cout << Ans[i] << ' ';
    return 0;
}

by Phrvth @ 2023-07-26 23:22:21

此贴结


by comcopy @ 2023-09-09 14:33:56

@Phrvth 什么问题求告知


by Phrvth @ 2023-09-10 00:29:20

@comcopy SIz 开大一点


|