CodeForces - 1406C - Link Cut Centroids (树的重心)

简介: 笔记

Link Cut Centroids



题意

对于一棵树 删除一条边再加上一条边使得新树只有一个重心


思路

此题转换成求树的重心树的重心最多有两个且有边相连 所以可以分为以下两种情况


此树只有一个重心任找与重心相连的一条边 删除再加上即可


找到了两个重心a,b 任选其中一个 例如选a 删除掉与 a 的除 b 外任意一个邻点的一条边 然后将这个邻点连到b 上去


代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1e9+7;
#define endl '\n'
using namespace std;
typedef  long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
inline LL lowbit(LL x) { return x & -x; }
const int N = 500010;
int n;
bool vis[N];
vector<int>v[N];
int t1, t2; //两个重心
int ans = INF;
int son[N];
void init() {
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    vis[i] = 0;
    son[i] = 0;
  }
  t1 = t2 = 0;
  ans = INF;
}
int dfs(int u) {
  vis[u] = true;
  int sum = 1, res = 0;
  for (int i = 0; i < v[u].size(); ++i) {
    int j = v[u][i];
    if (!vis[j]) {
      int s = dfs(j);
      sum += s;
      res = max(res, s);
    }
  }
  res = max(res, n - sum);
  if (ans >= res) {
    ans = res;
    son[u] = res;
    t2 = t1;
    t1 = u;
  }
  return sum;
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n - 1; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs(1); //找树的重心
  if (son[t1] != son[t2]) {
    printf("%d %d\n", t1, v[t1][0]);
    printf("%d %d\n", t1, v[t1][0]);
  }
  else {
    int u = 0;
    for (int i = 0; i < v[t1].size(); ++i) {
      int j = v[t1][i];
      if (j != t2) {
        u = j;
        break;
      }
    }
    printf("%d %d\n", t1, u);
    printf("%d %d\n", u, t2);
  }
  init();
}
int main() {
  int t; cin >> t;
  while(t--)
    solve();
  return 0;
}
目录
相关文章
|
10月前
|
机器学习/深度学习 存储 C++
【PAT甲级 - C++题解】1102 Invert a Binary Tree
【PAT甲级 - C++题解】1102 Invert a Binary Tree
52 0
|
10月前
|
机器学习/深度学习 C++
【PAT甲级 - C++题解】1151 LCA in a Binary Tree
【PAT甲级 - C++题解】1151 LCA in a Binary Tree
58 0
|
10月前
|
C++
【PAT甲级 - C++题解】1043 Is It a Binary Search Tree
【PAT甲级 - C++题解】1043 Is It a Binary Search Tree
60 0
【PAT甲级 - C++题解】1043 Is It a Binary Search Tree
牛客hot100--BM25---二叉树的后序遍历(简单难度)
牛客hot100--BM25---二叉树的后序遍历(简单难度)
63 0
牛客hot100--BM25---二叉树的后序遍历(简单难度)
牛客hot100--BM23---二叉树的前序遍历(简单难度)
牛客hot100--BM23---二叉树的前序遍历(简单难度)
103 0
牛客hot100--BM23---二叉树的前序遍历(简单难度)
|
Java Shell
Codeforces Round #746 (Div. 2) D - Hemose in ICPC ?(交互 二分 欧拉序)
Codeforces Round #746 (Div. 2) D - Hemose in ICPC ?(交互 二分 欧拉序)
135 0
|
人工智能 vr&ar
SPOJ - COT Count on a tree(主席树 LCA)
SPOJ - COT Count on a tree(主席树 LCA)
70 0
|
人工智能 BI
CF1398C. Good Subarrays(思维 前缀和)
CF1398C. Good Subarrays(思维 前缀和)
74 0
|
人工智能 BI Go
[Atcoder ABC222] F - Expensive Expense | 妙用树的直径 | Dijkstra
Problem Statement The Kingdom of AtCoder is composed of N towns and N−1 roads. The towns are labeled as Town 1, Town 2, …, Town N. Similarly, the roads are labeled as Road 1, Road 2, …, Road N−1. Road i connects Towns Ai and Bi bidirectionally, and you have to pay the toll of Ci to go through it.
178 0
[Atcoder ABC222] F - Expensive Expense | 妙用树的直径 | Dijkstra
[USACO | UPC] Liars and Truth Tellers | 拓展域并查集
题目描述 After spending so much time around his cows, Farmer John has started to understand their language. Moreover, he notices that among his N cows (2 ≤ N ≤ 1000 ), some always tell the truth while others always lie.
108 0