# CF1060E 题解()-其他

## CF1060E 题解()

### 代码

``````#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct Edge {int now, nxt;} e[N << 1];
{
e[++cur].now = v, e[cur].nxt = head[u];
}
ll sum[N], siz[N][2];
void dfs(int u, int fa)
{
siz[u][0] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].now;
if (v == fa) continue;
dfs(v, u);
siz[u][0] += siz[v][1], siz[u][1] += siz[v][0];
sum[u] += (sum[v] + siz[v][0]);
}
}
ll ans[N];
void DFS(int u, int fa, int dep)
{
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].now;
if (v == fa) continue;
ans[v] = ans[u] + siz[1][dep & 1] - (siz[v][0] + siz[v][1]);
DFS(v, u, dep + 1);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
}
dfs(1, 0), ans[1] = sum[1], DFS(1, 0, 0);
ll zlt = 0;
for (int i = 1; i <= n; i++) zlt += ans[i];
cout << zlt / 2;
return 0;
}
``````

————————

### 代码

``````#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct Edge {int now, nxt;} e[N << 1];
{
e[++cur].now = v, e[cur].nxt = head[u];
}
ll sum[N], siz[N][2];
void dfs(int u, int fa)
{
siz[u][0] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].now;
if (v == fa) continue;
dfs(v, u);
siz[u][0] += siz[v][1], siz[u][1] += siz[v][0];
sum[u] += (sum[v] + siz[v][0]);
}
}
ll ans[N];
void DFS(int u, int fa, int dep)
{
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].now;
if (v == fa) continue;
ans[v] = ans[u] + siz[1][dep & 1] - (siz[v][0] + siz[v][1]);
DFS(v, u, dep + 1);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);