记录编号	355229	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	Drench	是否通过	通过
代码语言	C++	运行时间	4.387 s
提交时间	2016-11-23 22:20:15	内存使用	65.15 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1000000;
struct xxx{int con, val, type;}node;
int n, m, u, v, cnt, w[MAXN];
int fa[MAXN], deep[MAXN], size[MAXN];
int top[MAXN], son[MAXN], ans[MAXN];
int mem1[MAXN * 2], mem2[MAXN * 2];
int *f = mem1 + MAXN, *g = mem2 + MAXN;
vector<int>G[MAXN];
vector<xxx>P[MAXN];
void dfs1(int cur, int father, int dep)
{
    fa[cur] = father;
    deep[cur] = dep;
    size[cur] = 1;
    son[cur] = 0;
    for(int i = 0; i < G[cur].size(); i++)
    {
        int nx = G[cur][i];
        if(nx == fa[cur]) continue;
        dfs1(nx, cur, dep + 1);
        size[cur] += size[nx];
        if(size[nx] > size[son[cur]])
            son[cur] = nx;
    }
}
void dfs2(int cur, int tp)
{
    top[cur] = tp;
    if(!son[cur]) return;
    dfs2(son[cur], tp);
    for(int i = 0; i < G[cur].size(); i++)
    {
        int nx = G[cur][i];
        if(nx == fa[cur] || nx == son[cur])
            continue;
        dfs2(nx, nx);
    }
}
int lca(int u, int v)
{
    int t1 = top[u], t2 = top[v];
    while(t1 != t2)
    {
        if(deep[t1] < deep[t2])
        {
            swap(u, v);
            swap(t1, t2);
        }
        u = fa[t1];
        t1 = top[u];
    }
    return deep[u] < deep[v] ? u : v;
}
void add(int x, int type, int val, int con)
{
    node.type = type;//0:up 1:down
    node.val = val;
    node.con = con;
    P[x].push_back(node);
}
void dfs(int cur)
{
    ans[cur] = f[deep[cur] + w[cur]]
            + g[deep[cur] - w[cur]];
    for(int i = 0; i < P[cur].size(); i++)
    {
        xxx nx = P[cur][i];
        if(nx.type) g[nx.con] += nx.val;
        else f[nx.con] += nx.val;
    }
    for(int i = 0; i < G[cur].size(); i++)
    {
        int nx = G[cur][i];
        if(nx != fa[cur]) dfs(nx);
    }
    ans[cur] = f[deep[cur] + w[cur]]
            + g[deep[cur] - w[cur]] - ans[cur];
}
int main()
{
    freopen("runninga.in", "r", stdin);
    freopen("runninga.out", "w", stdout);
    int sz = 64 << 20;
    char *p = (char*)malloc(sz) + sz;
    __asm__("movl %0, %%esp\n"::"r"(p));
    scanf("%d %d", &n, &m);
    for(int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1, 0, 0); dfs2(1, 1);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &u, &v);
        int LCA = lca(u, v),
            con1 = deep[u],
            con2 = 2 * deep[LCA] - deep[u];
        add(u, 0, 1, con1);
        add(LCA, 0, -1, con1);
        add(v, 1, 1, con2);
        if(LCA != 1) add(fa[LCA], 1, -1, con2);
    }
    dfs(1);
    for(int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    return 0;
}