NC14248 Treepath

题目地址：

https://ac.nowcoder.com/acm/problem/14248

基本思路：

很简单的一个树染色,感觉非常像上场div2 D的一部分,昨天刚补了那题,所以一下就想到了;
我们直接将图黑白染色,我们可以知道黑白染色之后,同种颜色之间的路径一定就是偶数的,所以我们把每种颜色的数量统计一下,假如黑色颜色节点有n个那么算下两两组合,就能组合出(n-1)!种路径,白色颜色节点同理,两者相加就是答案。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 1e18

const int maxn = 1e5 + 10;
struct Edge{
    int to,next;
}edge[maxn << 1];
int n,cnt,head[maxn];
void add_edge(int u,int v){
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
}
int color[maxn];
void dfs(int u,int p,int f) {//黑白染色;
  color[u] = f;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p) continue;
    dfs(to, u, 3 - f);
  }
}
int fac[maxn];
signed main() {
  IO;
  cnt = 0;
  mset(head,-1);
  cin >> n;
  rep(i,1,n) fac[i] = fac[i-1] + i;//预处理阶乘;
  rep(i,1,n-1){
    int u,v;
    cin >> u >> v;
    add_edge(u,v);
    add_edge(v,u);
  }
  dfs(1,0,1);
  int f1 = 0 ,f2 = 0;//记录两种颜色的数目;
  rep(i,1,n){
    if(color[i] == 1) f1++;
    else if(color[i] == 2) f2++;
  }
  int ans = fac[f1 - 1] + fac[f2 - 1];//两两连成一条路径;
  cout << ans << '\n';
  return 0;
}