#include < cstdio > #include < cstring > #include < cstdlib > #include < iostream > #include < vector > #include < queue > #include < stack > #include < map > #include < bitset > #include < set > #include < cmath > #include < algorithm > using namespace std;#define lowbit(x)((x) & ( - x))#define pi acos( - 1.0)#define eps 1e-8#define MOD 1000000007#define INF 1000000000#define mem(a, b) memset(a, b, sizeof(a))#define FOR(i, a, n) for (int i = a; i <= n; ++i)#define FDR(i, a, n) for (int i = a; i >= n; --i)#define bug puts("H");#define lch p << 1,
l,
mid#define rch p << 1 | 1,
mid + 1,
r#define mp make_pair#define pb push_back typedef pair < int,
int > PII;
typedef vector < int > VI;#pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL;
inline int Scan() {
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 x * f;
}
inline void Out(int a) {
if (a < 0) {
putchar(‘ - ‘);
a = -a;
}
if (a >= 10) Out(a / 10);
putchar(a % 10 + ‘0‘);
}
const int N = 200005;
//Code begin...
struct Edge {
int p,
next;
}
edge[N << 1];
int head[N],
cnt = 1;
int node[N],
siz[N],
num[N],
tmp,
sum[N],
mark;
int st[N << 1],
f[N],
col[N],
pos;
LL ans = 0;
void add_edge(int u, int v) {
edge[cnt].p = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int x, int fa) {
siz[x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
int v = edge[i].p;
if (v == fa) continue;
dfs(v, x);
siz[x] += siz[v];
}
}
void sol(int x, int fa) {
num[x] = siz[x]; --sum[node[x]];
if (node[x] == node[fa])--num[x];
if (col[node[x]]) tmp = st[col[node[x]]],
--num[tmp];
if (fa) {
if (col[node[fa]]) tmp = st[col[node[fa]]],
num[tmp] -= num[x];
f[++pos] = col[node[fa]];
col[node[fa]] = pos;
st[pos] = x;
}
for (int i = head[x]; i; i = edge[i].next) {
int v = edge[i].p;
if (v == fa) continue;
sol(v, x);
}
if (fa) {
ans += (LL) num[x] * (num[x] - 1) / 2;
sum[node[fa]] -= num[x];
col[node[fa]] = f[col[node[fa]]];
}
}
void init() {
mem(head, 0);
mem(siz, 0);
mem(num, 0);
mem(sum, 0);
mem(col, 0);
mem(f, 0);
ans = 0;
mark = 0;
cnt = 1;
pos = 0;
}
int main() {
int cas = 0,
n,
u,
v;
while (~scanf("%d", &n)) {
init();
FOR(i, 1, n) scanf("%d", node + i),
sum[node[i]] = n;
FOR(i, 1, n) if (sum[i])++mark;
FOR(i, 1, n - 1) scanf("%d%d", &u, &v),
add_edge(u, v),
add_edge(v, u);
dfs(1, 0);
sol(1, 0);
FOR(i, 1, n) ans += (LL) sum[i] * (sum[i] - 1) / 2;
ans = (LL) mark * n * (n - 1) / 2 - ans;
printf("Case #%d: %lld\n", ++cas, ans);
}
return 0;
}
来源: http://www.bubuko.com/infodetail-2228920.html