挂了，但感觉是对的说，可通过 S=1 或者 S=T 的数据

League丶翎 @ 2018-10-16 11:36:36

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 300000;

struct edge {int t , n;}e[N << 1];
int head[N] , tot;
void addedge(int u , int v) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    head[u] = tot;
}

int dep[N];
int w[N];
int n , m;

struct BZ {
    int fa[N][20];
    void prepare() {
        for(int j = 1 ; j < 20 ; ++ j)
            for(int i = 1 ; i <= n ; ++ i)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    int lca(int a , int b) {
        if(dep[a] < dep[b]) swap(a , b);
        for(int i = 19 ; i >= 0 ; -- i)
            if(dep[fa[a][i]] >= dep[b])
                a = fa[a][i];
        if(a == b) return a;
        for(int i = 19 ; i >= 0 ; -- i)
            if(fa[a][i] != fa[b][i]) {
                a = fa[a][i];
                b = fa[b][i];
            }
        return fa[a][0];
    }
}Jump;

void dfs(int x , int f) {
    Jump.fa[x][0] = f;
    dep[x] = dep[f] + 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        dfs(e[i].t , x);
    }
}

vector <int> up[N] , down[N];
vector <int> del_up[N] , del_down[N];

int ins_up[N] , ins_down[N];
int ans[N];

void DFS(int x , int f) {
    int UP = ins_up[w[x] + dep[x]];
    int DOWN = ins_down[w[x] - dep[x] + N];

    auto begin = up[x].begin() , end = up[x].end();
    for(auto i = begin ; i != end ; ++ i) ++ ins_up[*i];

    begin = down[x].begin(); end = down[x].end();
    for(auto i = begin ; i != end ; ++ i) ++ ins_down[*i];

    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        DFS(e[i].t , x);
    }

    ans[x] += ins_up[w[x] + dep[x]] - UP;
    ans[x] += ins_down[w[x] - dep[x] + N] - DOWN;

    begin = del_up[x].begin() , end = del_up[x].end();
    for(auto i = begin ; i != end ; ++ i) -- ins_up[*i];

    begin = del_down[x].begin(); end = del_down[x].end();
    for(auto i = begin ; i != end ; ++ i) -- ins_down[*i];
}

int main() {
    freopen("work.in" , "r" , stdin);
    n = read(); m = read();
    for(int i = 1 ; i < n ; ++ i) {
        int x = read() , y = read();
        addedge(x , y);
        addedge(y , x);
    }
    dfs(1 , 0);
    Jump.prepare();
    for(int i = 1 ; i <= n ; ++ i) w[i] = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int x = read() , y = read();
        int lca = Jump.lca(x , y);

        up[x].push_back(dep[x]);
        del_up[lca].push_back(dep[x]);

        down[y].push_back(dep[x] - 2 * dep[lca] + N);
        del_down[lca].push_back(dep[x] - 2 * dep[lca] + N);

        if(dep[x] - dep[lca] == w[lca]) -- ans[lca];
    }
    DFS(1 , 0);
    for(int i = 1 ; i <= n ; ++ i) printf("%d\n" , ans[i]);
    return 0;
}

by League丶翎 @ 2018-10-16 12:08:14

找到问题了

数组开小

丢人...

AC 代码

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 300000;

struct edge {int t , n;}e[N << 1];
int head[N] , tot;
void addedge(int u , int v) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    head[u] = tot;
}

int dep[N];
int w[N];
int n , m;

struct BZ {
    int fa[N][20];
    void prepare() {
        for(int j = 1 ; j < 20 ; ++ j)
            for(int i = 1 ; i <= n ; ++ i)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    int lca(int a , int b) {
        if(dep[a] < dep[b]) swap(a , b);
        for(int i = 19 ; i >= 0 ; -- i)
            if(dep[fa[a][i]] >= dep[b])
                a = fa[a][i];
        if(a == b) return a;
        for(int i = 19 ; i >= 0 ; -- i)
            if(fa[a][i] != fa[b][i]) {
                a = fa[a][i];
                b = fa[b][i];
            }
        return fa[a][0];
    }
}Jump;

void dfs(int x , int f) {
    Jump.fa[x][0] = f;
    dep[x] = dep[f] + 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        dfs(e[i].t , x);
    }
}

vector <int> up[N] , down[N];
vector <int> del_up[N] , del_down[N];

int ins_up[N << 1] , ins_down[N << 1];
int ans[N];

void DFS(int x , int f) {
    ans[x] -= ins_up[w[x] + dep[x]];
    ans[x] -= ins_down[w[x] - dep[x] + n];

    auto begin = up[x].begin() , end = up[x].end();
    for(auto i = begin ; i != end ; ++ i) ++ ins_up[*i];

    begin = down[x].begin(); end = down[x].end();
    for(auto i = begin ; i != end ; ++ i) ++ ins_down[*i];

    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        DFS(e[i].t , x);
    }

    ans[x] += ins_up[w[x] + dep[x]];
    ans[x] += ins_down[w[x] - dep[x] + n];

    begin = del_up[x].begin() , end = del_up[x].end();
    for(auto i = begin ; i != end ; ++ i) -- ins_up[*i];

    begin = del_down[x].begin(); end = del_down[x].end();
    for(auto i = begin ; i != end ; ++ i) -- ins_down[*i];
}

int main() {
    freopen("work.in" , "r" , stdin);
    n = read(); m = read();
    for(int i = 1 ; i < n ; ++ i) {
        int x = read() , y = read();
        addedge(x , y);
        addedge(y , x);
    }
    dfs(1 , 0);
    Jump.prepare();
    for(int i = 1 ; i <= n ; ++ i) w[i] = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int x = read() , y = read();
        int lca = Jump.lca(x , y);

        up[x].push_back(dep[x]);
        del_up[lca].push_back(dep[x]);

        down[y].push_back(dep[x] - 2 * dep[lca] + n);
        del_down[lca].push_back(dep[x] - 2 * dep[lca] + n);

        if(dep[x] - dep[lca] == w[lca]) -- ans[lca];
    }
    DFS(1 , 0);
    for(int i = 1 ; i <= n ; ++ i) printf("%d " , ans[i]);
    return 0;
}

by Fraction @ 2018-10-16 12:16:53

orz

by Eason_AC @ 2018-10-16 12:49:52

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈可以抄了

by shadowice1984 @ 2018-10-16 14:34:29

不要加"的说"这类东西啊……汉语又不是黏着语听起来挺别扭的……