记录编号	432075	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 简单的最近公共祖先	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	1.299 s
提交时间	2017-08-02 20:07:08	内存使用	12.01 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

//#ifndef LOCAL
#define MAXN (1000010)
//#else
//#define MAXN (1010)
//#endif
typedef long long LL;

struct EDGE{ 
    int to;
    EDGE *ne;

    EDGE() { ;}
    EDGE(int _to, EDGE *_ne) { 
        to = _to, ne = _ne;
    }
};

EDGE *head[MAXN];
inline void add_edge(int fr, int to);
void dfs(int u);

int siz[MAXN], w[MAXN], N;
LL ans;

int main() { 
#ifndef LOCAL
    freopen("easy_LCA.in", "r", stdin);
    freopen("easy_LCA.out", "w", stdout);
#endif
    N = read();
    for(int i = 1, *j = w + 1; i <= N; ++i, ++j) *j = read();
    for(int i = 1; i < N; ++i) add_edge(read(), read());
    dfs(1);
    printf("%lld\n", ans);
    return 0;
}

inline void add_edge(int fr, int to) { 
    head[fr] = new EDGE(to, head[fr]);
    head[to] = new EDGE(fr, head[to]);
    return ;
}

void dfs(int u) { 
    int &tmp = siz[u];
    tmp = 1;
    register int v;
    for(register EDGE *e = head[u]; e; e = e->ne) { 
        if(siz[v = e->to]) continue;
        dfs(v);
        ans += (LL)tmp * (LL)siz[v] * (LL)w[u];
        tmp += siz[v];
    }
    ans += w[u];
    return ;
}