【有数据】蒟蒻不是刚学OI不是妹子蜜汁70求助dalao

// #pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 300005
#define maxe (maxn << 1)

using namespace std;

bool vis[maxn];
int n, m, w[maxn], fa[maxn][21], dep[maxn];
int c[maxn << 2], f[maxn][21], cf[maxn], st[maxn], cc[maxn << 2], in[maxn];
int lnk[maxn], nxt[maxe], son[maxe], tot = 1;
int lk[maxn], nx[maxe], so[maxe], to = 1;
int ln[maxn], nt[maxe], sn[maxe], tt = 1;
int ans[maxn], res = 0, maxw = 0, id[maxn];

class ply
{
public:
    int s, t, mid, tim;
}a[maxn];

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

void adde(int x, int y)
{
    son[++tot] = y, nxt[tot] = lnk[x], lnk[x] = tot;
}

void ade(int x, int y)
{
    so[++to] = y, nx[to] = lk[x], lk[x] = to;
}

void add(int x, int y)
{
    sn[++tt] = y, nt[tt] = ln[x], ln[x] = tt;
}

void DFS(int now, int pre, int dp)
{
    fa[now][0] = pre, dep[now] = dp;
    for (int i = 1; i <= 19; ++i)
        fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for (int j = lnk[now]; j; j = nxt[j])
    {
        if (son[j] == pre)
            continue;
        DFS(son[j], now, dp + 1);
    }
}

int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; --i)
    {
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    }
    if (x == y)
        return x;
    for (int i = 19; i >= 0; --i)
    {
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

void DFS_Up(int now)
{
    f[now][0] = c[w[now] + dep[now]];
    ade(f[now][0], now);
    c[w[now] + dep[now]] = now;
    int lst = cc[w[now] + dep[now]];
    cc[w[now] + dep[now]] = now;
    st[now] = cc[dep[now]];
    for (int i = 1; i <= 19; ++i)
        f[now][i] = f[f[now][i - 1]][i - 1];
    for (int j = lnk[now]; j; j = nxt[j])
    {
        if (son[j] == fa[now][0])
            continue;
        DFS_Up(son[j]);
    }
    c[w[now] + dep[now]] = f[now][0];
    cc[w[now] + dep[now]] = lst;
}

void DFS_Dw(int now)
{
    f[now][0] = c[w[now] + dep[now]];
    ade(f[now][0], now);
    c[w[now] + dep[now]] = now;
    int lst = cc[w[now] + dep[now]];
    cc[w[now] + dep[now]] = now;
    for (int j = ln[now]; j; j = nt[j])
        st[sn[j]] = cc[dep[now] + a[sn[j]].tim];
    for (int i = 1; i <= 19; ++i)
        f[now][i] = f[f[now][i - 1]][i - 1], f[now][i + 1] = 0;
    for (int j = lnk[now]; j; j = nxt[j])
    {
        if (son[j] == fa[now][0])
            continue;
        DFS_Dw(son[j]);
    }
    c[w[now] + dep[now]] = f[now][0];
    cc[w[now] + dep[now]] = lst;
}

void Count(int now)
{
    for (int j = lk[now]; j; j = nx[j])
    {
        if (so[j] == f[now][0])
            continue;
        Count(so[j]);
    }
    res += cf[now];
    cf[now] = 0;
    ans[now] += res;
}

int main()
{
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i < n; ++i)
    {
        int x = read(), y = read();
        adde(x, y), adde(y, x);
    }
    for (int i = 1; i <= n; ++i)
        w[i] = read(), maxw = max(maxw, w[i]);
    dep[0] = -1;
    DFS(1, 0, 0);
    for (int i = 1; i <= m; ++i)
    {
        a[i].s = read(), a[i].t = read();
        a[i].mid = lca(a[i].s, a[i].t);
        a[i].tim = dep[a[i].s] - dep[a[i].mid] + dep[a[i].t] - dep[a[i].mid];
        a[i].tim = maxw - a[i].tim;
    }
    DFS_Up(1);
    for (int i = 1; i <= m; ++i)
    {
        int s = st[a[i].s];
        if (dep[s] > dep[a[i].mid])
        {
            cf[s]++;
            for (int j = 19; j >= 0; --j)
            {
                if (dep[f[s][j]] >= dep[a[i].mid])
                    s = f[s][j];
            }
            cf[f[s][0]]--;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        res = 0;
        if (!f[i][0])
            Count(i);
    }
    for (int i = 1; i <= n; ++i)
        w[i] = maxw - w[i], lk[i] = 0, nx[i] = nx[i + n] = 0;
    for (int i = 1; i <= m; ++i)
        add(a[i].t, i);
    to = 1;
    DFS_Dw(1);
    for (int i = 1; i <= m; ++i)
    {
        int s = st[i];
        if (dep[s] >= dep[a[i].mid])
        {
            cf[s]++;
            for (int j = 19; j >= 0; --j)
            {
                if (dep[f[s][j]] >= dep[a[i].mid])
                    s = f[s][j];
            }
            cf[f[s][0]]--;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        res = 0;
        if (!f[i][0])
            Count(i);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}

评测详细信息

NOIP2016复赛测试数据