center of gravity of the tree
Given a tree, the tree contains n nodes (numbered 1～n) and n?1 undirected edges. Please find the center of gravity of the tree, and output the maximum number of points in the remaining connected blocks after the center of gravity is deleted.
Definition of center of gravity: center of gravity refers to a node in the tree. If the point is deleted and the maximum number of points in the remaining connected blocks is the smallest, then this node is called the center of gravity of the tree.
input format
The first line contains the integer n, the number of nodes in the tree.
Next n?1 lines, each line contains two integers a and b, indicating that there is an edge between point a and point b.
output format
Output an integer m, which represents the maximum number of points in the remaining connected blocks after the center of gravity is deleted.
data range
1≤n≤105
input sample
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
Sample output:
4
Solution
The code above implements an algorithm to find the gravity of a tree, which is defined as the minimum possible value of the maximum subtree size when the tree is rooted at any node. The algorithm uses a depth-first search to traverse the tree and compute the size of each subtree.
The program first reads an integer n from standard input, which represents the number of nodes in the tree. It then reads n-1 pairs of integers a code> and b, which represent the edges of the tree. The program assumes that the tree is undirected, so it adds both (a, b) and ( b, a) to the adjacency list.
The program then calls the dfs function with the root node 1. The dfs function takes an integer u as input , which represents the current node being visited. The function first marks u as visited by setting state[u] to true. It then initializes two variables sum code> and res to 1 and 0, respectively. The variable sum represents the size of the subtree rooted at u, and is initialized to 1 because u is included in its own subtree. The variable res represents the maximum subtree size of any child of u, and is initialized to 0.
The function then iterates over all edges that start at u, and for each edge (u, v), it checks if v has not been visited yet. If v has not been visited, the function recursively calls dfs with v as the input, and stores the return value in a variable s. The function then updates res to be the maximum of res and s, and updates sum to be the sum of sum and s.
After the loop over all edges is finished, the function computes the maximum subtree size of u by subtracting sum from n, which is the total number of nodes in the tree. It then updates the global variable ans to be the minimum of ans and the maximum subtree size of u. Finally, the function returns sum to its parent.
The program outputs the value of ans to standard output, which represents the gravity of the tree.
Overall, this code is a simple and efficient implementation of an algorithm to find the gravity of a tree. However, it assumes that the tree is connected and undirected, and does not check for duplicate edges or self-loops. If the tree is directed , or if duplicate edges or self-loops are allowed, additional checks and modifications may be necessary. Additionally, the program uses global variables to store the adjacency list and other state information, which may make it harder to reuse or modify the code in other contexts.
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
The code above defines a function add that is used to add an edge to an adjacency list representation of a graph. The function takes two integers a and b as input, which represent the endpoints of the edge to be added.
The function assumes that the graph is represented using an adjacency list, where h[i] is a pointer to the head of the linked list of edges that start at vertex i. The function also assumes that the edges are stored in an array e, and the next pointers for the linked list are stored in an array ne.
To add an edge from vertex a to vertex b, the function first sets e[idx] to b, where idx is a global variable that keeps track of the next available index in the e array. This stores the endpoint of the edge in the e array.
The function then sets ne[idx] to h[a], which makes the new edge the head of the linked list of edges that start at vertex a. Finally, the function updates h[a] to idx, which makes the new edge the head of the linked list.
Overall, this code is a simple and efficient implementation of adding an edge to an adjacency list representation of a graph. However, it assumes that the graph is undirected, and does not check for duplicate edges or self-loops. If the graph is directed , or if duplicate edges or self-loops are allowed, additional checks and modifications may be necessary.
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int ans = N;
int e[N * 2], h[N], ne[N * 2], idx;
bool state[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int u) {
state[u] = true;
int sum = 1, res = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!state[j]) {
int s = dfs(j);
res = max(res, s);
sum + = s;
}
}
res = max(res, n - sum);
ans = min(res, ans);
return sum;
}
int main() {
cin. tie(nullptr);
cout. tie(nullptr);
ios::sync_with_stdio(false);
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ ) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int ans = N;
vector<vector<int>> G(N);
bool st[N];
int dfs(int u) {
st[u] = true;
int sum = 1;
int res = 0;
for (auto x : G[u]) {
if (!st[x]) {
int s = dfs(x);
res = max(res, s);
sum + = s;
}
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
int main() {
cin. tie(nullptr);
cout. tie(nullptr);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n - 1; i ++ ) {
int a, b;
cin >> a >> b;
G[a].push_back(b), G[b].push_back(a);
}
dfs(1);
cout << ans << endl;
return 0;
}
Summary
The answer to this question looks for a minimum maximum value, and the minimum maximum value among the remaining branches when a certain node is removed. Traverse each node (dfs) separately, find the remaining maximum value after removing this node, and then compare and remove the minimum value of each node in turn.