求助大佬,为啥第13个点WA了,95分!!

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

我不是导神 @ 2019-02-09 19:43:57

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define N 300000

using namespace std;

int n, m, t, tot = 0;
int hd[N], nxt[N*2], ver[N*2];
int f[N][20], d[N], w[N], v[N], c1[N], c2[N];
int ans[N];
queue<int> q;
vector<int> a1[N], b1[N], a2[N], b2[N]; 

inline int rd() {
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') x = x*10 + ch - '0', ch = getchar();
    return f*x;
}

void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = hd[x], hd[x] = tot;
}

void bfs() {
    d[1] = 1, q.push(1);
    while(q.size()) {
        int x = q.front();
        q.pop();
        for(int i = hd[x]; i; i = nxt[i]) {
            int y = ver[i];
            if(d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1; j <= t; j++) {
                f[y][j] = f[f[y][j - 1]][j - 1];
            }
            q.push(y);
        }
    }
}

int lca(int x, int y) {
    if(d[x] > d[y]) swap(x, y);
    for(int i = t; i >= 0; i--) {
        if(d[f[y][i]] >= d[x]) y = f[y][i];
    }
    if(x == y) return x;
    for(int i = t; i >= 0; i--) {
        if(f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

void dfs(int x) {
    int val1 = c1[d[x] + w[x]], val2 = c2[w[x] - d[x] + n];
    v[x] = 1;
    for(int i = hd[x]; i; i = nxt[i]) {
        int y = ver[i];
        if(v[y]) continue;
        dfs(y);
    }
    for(int i = 0; i < a1[x].size(); i++) c1[a1[x][i]]++;
    for(int i = 0; i < b1[x].size(); i++) c1[b1[x][i]]--;
    for(int i = 0; i < a2[x].size(); i++) c2[a2[x][i] + n]++;
    for(int i = 0; i < b2[x].size(); i++) c2[b2[x][i] + n]--;
    ans[x] += c1[d[x] + w[x]] - val1 + c2[w[x] - d[x] + n] - val2;
}

int main() {
//  freopen("run.in","r",stdin);
//  freopen("run.out","w",stdout);
    n = rd(), m = rd();
    t = (int)(log(n) / log(2)) + 1;
    for(int i = 1; i < n; i++) {
        int x = rd(), y = rd();
        add(x, y), add(y, x);
    }
    for(int i = 1; i <= n; i++) w[i] = rd();
    bfs();
    for(int i = 1; i <= m; i++) {
        int x = rd(), y = rd();
        int z = lca(x, y);
        a1[x].push_back(d[x]);
        b1[f[z][0]].push_back(d[x]);
        a2[y].push_back(d[x] - 2 * d[z]);
        b2[z].push_back(d[x] - 2 * d[z]); 
    }
    dfs(1);
    for(int i = 1; i < n; i++) printf("%d ", ans[i]);
    printf("%d\n", ans[n]);
    return 0;
}

by ZQYZQY @ 2019-10-17 11:12:41

+1


by ZQYZQY @ 2019-10-17 11:13:09

@我不是导神 大佬有查出吗?


|