【每日一题】Treepath 题解

Solution

一开始感觉是个树形dp 因为偶数总能从奇数转换过来
但是这个思路 我连样例都过不了(真菜
我们考虑下从深度角度出发, 以 1 为根求出全部深度
那么偶数层到偶数层 距离为偶数
奇数到奇数层 距离距离也为偶数
那么我们求出奇数层节点为l, 偶数层节点个数为r
ans = (l - 1) * l / 2 + (r - 1) * r / 2
时间复杂度

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int tot, head[N];
struct Edge{
  int v, nextz;
}edge[N << 1];
int dep[N];
void addedge(int u, int v){
  edge[tot].v = v;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
bool vis[N];
void bfs(int root){
  dep[root] = 1;
  queue<int> q;
  q.push(root);
  while(!q.empty()){
    int u = q.front();
    q.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].nextz){
      int v = edge[i].v;
      if(!vis[v]){
        dep[v] = dep[u] + 1;
        q.push(v);
      }
    } 
  }
}
int main(){
  memset(head, -1, sizeof(head));
  int n;
  cin >> n;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    addedge(u, v);
    addedge(v, u);
  }
  bfs(1);
  ll ans = 0;
  ll l = 0, r = 0;
  for(int i = 1; i <= n; i++){
    if(dep[i] & 1) l++;
    else r++;   
  }
  cout << r * (r - 1) / 2 + l * (l - 1) / 2 << "\n";
  return 0;
}