1. Multiple Choice Questions (2 points each, total 30 points)
Question 1: Which of the following statements about classes is incorrect ( )?
A. Constructors cannot be declared as virtual functions, but destructors can.B. If function parameters are declared as references to a class, the copy constructor of that class will not be called during the call.C. Static methods belong to the class rather than a specific object, so it is recommended to call them using ClassName::method(…).D. Regardless of whether the base class destructor is a virtual function, derived class objects can be correctly deleted through base class pointers/references.
Answer: ❌ DExplanation:
-
Option A: Correct, constructors are used to initialize objects and cannot be declared as virtual functions; destructors can be declared as virtual functions to support polymorphic deletion.
-
Option B: Correct, reference passing only binds to the object without copying it, hence the copy constructor is not called.
-
Option C: Correct, static methods are class-level members and do not depend on object instances, so it is recommended to call them using “ClassName::method”.
-
Option D: Incorrect, if the base class destructor is not a virtual function, deleting a derived class object through a base class pointer will only call the base class destructor, leading to memory leaks as the derived class resources cannot be released.
Question 2: Assuming the variable veh is an instance of the class Car, we can call veh.move() because object-oriented programming has the property of ( ).
class Vehicle {
private:
string brand;
public:
Vehicle(string b) : brand(b) {}
void setBrand(const string &b) { brand = b; }
string getBrand() const { return brand; }
void move() const {
cout << brand << " is moving..." << endl;
}
};
class Car : public Vehicle {
private:
int seatCount;
public:
Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
void showInfo() const {
cout << "This car is a " << getBrand() << " with " << seatCount << " seats." << endl;
}
};A. InheritanceB. EncapsulationC. PolymorphismD. Linking
Answer: ✅ AExplanation:
-
The class Car inherits from the Vehicle class through
public Vehicle, inheriting the public member function move() from Vehicle. -
veh is an instance of Car, and can directly call the inherited move(), reflecting the object-oriented property of “inheritance”.
-
Encapsulation hides internal implementation and exposes interfaces; polymorphism is the same interface with different implementations, neither of which is involved in this question, hence option A is selected.
Question 3: In the following code, v1 and v2 call the same interface move(), but the output results are different, which reflects the property of object-oriented programming ( ).
class Vehicle {
private:
string brand;
public:
Vehicle(string b) : brand(b) {}
void setBrand(const string &b) { brand = b; }
string getBrand() const { return brand; }
virtual void move() const {
cout << brand << " is moving..." << endl;
}
};
class Car : public Vehicle {
private:
int seatCount;
public:
Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
void showInfo() const {
cout << "This car is a " << getBrand() << " with " << seatCount << " seats." << endl;
}
void move() const override {
cout << getBrand() << " car is driving on the road!" << endl;
}
};
class Bike : public Vehicle {
public:
Bike(string b) : Vehicle(b) {}
void move() const override {
cout << getBrand() << " bike is cycling on the path!" << endl;
}
};
int main() {
Vehicle* v1 = new Car("Toyota", 5);
Vehicle* v2 = new Bike("Giant");
v1->move();
v2->move();
delete v1;
delete v2;
return 0;
}A. InheritanceB. EncapsulationC. PolymorphismD. Linking
Answer: ✅ CExplanation:
-
The base class Vehicle’s move() is declared as a virtual function, and the derived classes Car and Bike override this function.
-
The base class pointers v1 and v2 point to derived class objects, and when calling move(), the corresponding derived class implementation is executed, resulting in different outputs.
-
This “same interface, different implementation” characteristic is the “polymorphism” of object-oriented programming, hence option C is selected.
Question 4: The operational characteristic of a stack is ( ).
A. First In First OutB. Last In First OutC. Random AccessD. Double-ended Access
Answer: ✅ BExplanation:
-
A stack is a linear data structure that follows the “Last In First Out (LIFO)” principle, allowing only insertions (push) and deletions (pop) at the top of the stack.
-
Option A is a characteristic of queues; option C is a characteristic of arrays; option D is a characteristic of double-ended queues (deque), hence option B is selected.
Question 5: Circular queues are commonly used to implement data buffering. Assuming a circular queue has a capacity of 5 (i.e., it can hold a maximum of 4 elements, leaving one position to distinguish between empty and full), after performing the operations: enqueue data 1, 2, 3, dequeue 1 data, and then enqueue data 4 and 5, what is the order of elements from the front to the rear of the queue ( )?
A. [2, 3, 4, 5]B. [1, 2, 3, 4]C. [3, 4, 5, 2]D. [2, 3, 5, 4]
Answer: ✅ AExplanation: The core of a circular queue: simulated using an array, with the front pointer (front) and rear pointer (rear) indicating the range of the queue. With a capacity of 5, it can actually store 4 elements (when rear + 1 == front, it is full).
-
Initial state: front = 0, rear = 0;
-
Enqueue 1, 2, 3: rear changes to 1, 2, 3, queue elements are [1, 2, 3];
-
Dequeue 1 data: front changes to 1, queue elements are [2, 3];
-
Enqueue 4, 5: rear changes to 4, 0 (mod 5 operation), queue elements are [2, 3, 4, 5];At this point, the order from front to rear is 2 → 3 → 4 → 5, hence option A is selected.
Question 6: What type of tree is constructed by the following function createTree()?
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* createTree() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
return root;
}A. Full Binary TreeB. Complete Binary TreeC. Binary Search TreeD. None of the above
Answer: ✅ BExplanation:
-
A full binary tree has all leaf nodes at the same level, and non-leaf nodes have two children (the right child of the root node has 0 children, so it is not a full binary tree);
-
A complete binary tree has all nodes numbered in level order, and all nodes correspond one-to-one with the nodes of a full binary tree of the same height (the numbering 1-5 in this question corresponds to root, left, right, left-left, left-right, satisfying the definition of a complete binary tree);
-
A binary search tree has all node values in the left subtree < root node value, and all node values in the right subtree > root node value (in this question, the right subtree 3 > 1, but the children 4 and 5 of the left subtree 2 are both > 2, which does not satisfy);hence option B is selected.
Question 7: Given the inorder traversal of a binary tree is [D, B, E, A, F, C], and the preorder traversal is [A, B, D, E, C, F], what is the postorder traversal result of this binary tree ( )?
A. [D, E, B, F, C, A]B. [D, B, E, F, C, A]C. [D, E, B, C, F, A]D. [B, D, E, F, C, A]
Answer: ✅ AExplanation: Based on the preorder and inorder traversals, we can deduce the structure of the binary tree:
-
The first element of the preorder traversal is the root node: A is the root;
-
In the inorder traversal, the left side of A [D, B, E] is the left subtree, and the right side [F, C] is the right subtree;
-
The first element of the left subtree in preorder traversal is B (after A in preorder traversal comes B), B is the root of the left subtree; in the inorder traversal, the left side of B [D] is the left subtree of B, and the right side [E] is the right subtree of B;
-
The first element of the right subtree in preorder traversal is C (after E in preorder traversal comes C), C is the root of the right subtree; in the inorder traversal, the left side [F] is the left subtree of C, and there is no right side;
-
The structure of the binary tree is: A (left: B, right: C); B (left: D, right: E); C (left: F, right: none);the postorder traversal order (left → right → root): D → E → B → F → C → A, hence option A is selected.
Question 8: A complete binary tree can be stored continuously and efficiently using an array. If nodes are numbered starting from 1, then for a node i with two child nodes, ( ).
A. The left child is located at 2i, and the right child is located at 2i + 1B. The leaf nodes of a complete binary tree can appear in any position in the last layerC. All nodes have two childrenD. The left child is located at 2i + 1, and the right child is located at 2i + 2
Answer: ✅ AExplanation: The array storage rule for complete binary trees (node numbering starts from 1):
-
The left child of node i is numbered 2i, and the right child is numbered 2i + 1 (option A is correct, D is incorrect);
-
Leaf nodes of a complete binary tree are concentrated in the last two layers, and the leaf nodes in the last layer are arranged continuously from left to right, not in arbitrary positions (option B is incorrect);
-
A complete binary tree allows the last layer to be incomplete, hence there can be nodes with only left children or no children (option C is incorrect);hence option A is selected.
Question 9: Given the character set {a, b, c, d, e, f} with frequencies {5, 9, 12, 13, 16, 45}, which of the following groups could be the corresponding Huffman encoding? (Non-leaf node left branches are marked as 0, right branches as 1, and swapping left and right does not affect correctness).
A. a: 00; b: 01; c: 10; d: 110; e: 111; f: 0B. a: 1100; b: 1101; c: 100; d: 101; e: 111; f: 0C. a: 000; b: 001; c: 01; d: 10; e: 110; f: 111D. a: 10; b: 01; c: 100; d: 101; e: 111; f: 0
Answer: ✅ BExplanation: The core of Huffman encoding: characters with higher frequencies have shorter encodings, and no encoding is a prefix of another (prefix encoding property).
-
Frequency order: f(45) > e(16) > d(13) > c(12) > b(9) > a(5);
-
During the construction of the Huffman tree, f has the highest frequency and should have the shortest encoding (1 bit, such as 0 or 1), excluding option C (f encoding 111, 3 bits);
-
Option A: a(00) and f(0), f’s encoding is a prefix of a, which does not comply with the prefix encoding rule;
-
Option D: a(10) and c(100), a’s encoding is a prefix of c, which does not comply with the prefix encoding rule;
-
Option B: All encodings have no prefix conflicts, and the higher frequency f(0, 1 bit), e(111, 3 bits), d(101, 3 bits) have shorter encodings, complying with Huffman encoding characteristics, hence option B is selected.
Question 10: The following code generates Gray code, what should be filled in the blank ( )?
vector<string> grayCode(int n) {
if (n == 0) return {"0"};
if (n == 1) return {"0", "1"};
vector<string> prev = grayCode(n - 1);
vector<string> result;
for (string s : prev) {
result.push_back("0" + s);
}
for (_______________) { // Fill code here
result.push_back("1" + prev[i]);
}
return result;
}A. int i = 0; i < prev.size(); i++B. int i = prev.size() – 1; i >= 0; i–C. auto s : prevD. int i = prev.size() / 2; i < prev.size(); i++
Answer: ✅ BExplanation:The generation rule for Gray code: n-bit Gray code = (n-1 bit Gray code prefixed with “0”) + (n-1 bit Gray code reversed prefixed with “1”).
-
Example: when n=1, the Gray code is [“0”, “1”];
-
When n=2: first add “0” to get [“00”, “01”], then reverse the n=1 encoding [“1”, “0”] and add “1” to get [“11”, “10”], the final result is [“00”, “01”, “11”, “10”]; the second loop in the code needs to traverse prev in reverse, hence from prev.size() – 1 to 0, hence option B is selected.
Question 11: Please complete the depth-first traversal code for the following tree, what should be filled in the blank ( )?
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
// Fill code here: ______<TreeNode*> temp
void dfs(TreeNode* root) {
if (!root) return;
temp.push(root);
while (!temp.empty()) {
TreeNode* node = temp.top();
temp.pop();
cout << node->val << " ";
if (node->right) temp.push(node->right);
if (node->left) temp.push(node->left);
}
}A. vectorB. listC. queueD. stack
Answer: ✅ DExplanation: Depth-first traversal (DFS) iterative implementation relies on the “stack” data structure, following the “last in, first out” principle:
-
First, push the root node onto the stack, pop the node and visit it;
-
First push the right child onto the stack, then the left child (ensuring the left child is visited first, complying with the preorder traversal order);the operations of temp in the code are push (push onto stack), top (get top of stack), pop (pop from stack), all of which are core operations of a stack, hence option D is selected.
Question 12: Let n be the number of nodes in the tree, the time complexity of the following code implementing breadth-first traversal of the tree is ( ).
void bfs(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}A. O(n)B. O(n²)C. O(log n)D. O(2ⁿ)
Answer: ✅ AExplanation: Breadth-first traversal (BFS) relies on the “queue”; each node is enqueued and dequeued once, with n access times.
-
The time complexity of the queue’s push and pop operations is O(1), and the overall number of operations is proportional to the number of nodes n, hence the time complexity is O(n), hence option A is selected.
Question 13: In a binary search tree (BST), when searching for the element 50 starting from the root node: if the root value is 60, the next step should be to search ( ).
A. Left SubtreeB. Right SubtreeC. RandomlyD. Root Node
Answer: ✅ AExplanation: The search rule in a binary search tree:
-
If the target value < root node value, search the left subtree;
-
If the target value > root node value, search the right subtree;
-
In this question, the target value 50 < root node value 60, hence the next step should search the left subtree, hence option A is selected.
Question 14: When deleting a node in a binary search tree that has two children, what should be filled in the blank, where findMax and findMin are functions for finding the maximum and minimum values in the tree, respectively?
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left) return root->right;
if (!root->right) return root->left;
// Fill code here: TreeNode* temp =
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
return root;
}
return root;
}A. root->leftB. root->rightC. findMin(root->right)D. findMax(root->left)
Answer: ✅ CExplanation: When deleting a node with two children in a binary search tree, it is necessary to maintain the sorting property of the tree, commonly using the “successor node replacement” strategy:
-
The successor node is the minimum value node in the right subtree of the node to be deleted (findMin(root->right)), whose value is greater than all node values in the left subtree of the node to be deleted and less than the values of other nodes in the right subtree;
-
Steps: 1. Find the successor node temp; 2. Replace the value of the node to be deleted with temp’s value; 3. Delete the temp node in the right subtree;option D (findMax(root->left)) is the predecessor node replacement strategy, and the subsequent delete operation is root->right, hence corresponding to the successor node, hence option C is selected.
Question 15: Given n items and a maximum weight of W for a backpack, each item has a weight wt[i] and a value val[i], and the items cannot be divided (0-1 backpack). The goal is to select several items to put into the backpack to maximize the total value while ensuring the total weight does not exceed W. What should be filled in the blank ( )?
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; ++i) {
for (int w = W; w >= wt[i]; --w) {
// Fill code here
}
}
return dp[W];
}A. dp[w] = max(dp[w], dp[w] + val[i]);B. dp[w] = dp[w – wt[i]] + val[i];C. dp[w] = max(dp[w – 1], dp[w – wt[i]] + val[i]);D. dp[w] = max(dp[w], dp[w – wt[i]] + val[i]);
Answer: ✅ DExplanation: The core of the 0-1 backpack dynamic programming is the “state transition equation”:
-
dp[w] represents the maximum value that can be accommodated in the backpack with weight w;
-
For the i-th item, there are two choices: not to put it (dp[w] remains unchanged) or to put it (dp[w – wt[i]] + val[i], i.e., the maximum value of weight w – wt[i] plus the current item value);
-
We need to take the maximum of the two choices, and the inner loop traverses from W in reverse (to avoid selecting the same item multiple times);option A adds val[i] repeatedly, which is incorrect; option B does not take the maximum value, which is incorrect; option C compares dp[w-1] which is meaningless, which is incorrect; hence option D is selected.
2. True/False Questions (2 points each, total 20 points)
Question 1: When a base class may be used polymorphically, its destructor should be declared as a virtual function.
Answer: ✅ CorrectExplanation: If the base class destructor is not a virtual function, when deleting a derived class object through a base class pointer, only the base class destructor will be called, and the derived class resources cannot be released, leading to memory leaks.When the base class is used polymorphically (e.g., a base class pointer points to a derived class object), the destructor must be declared as a virtual function to ensure the derived class destructor is called correctly, hence it is correct.
Question 2: Huffman coding is an optimal prefix code, and the encoding result is unique.
Answer: ❌ IncorrectExplanation:
-
Huffman coding is an “optimal prefix code” (with the shortest average encoding length), but the encoding result is not unique.
-
The reason: during the construction of the Huffman tree, when two nodes have the same frequency, the choice of left and right subtrees can be swapped, leading to different 0/1 encoding orders, hence the encoding result is not unique, which is incorrect.
Question 3: A complete binary tree with 100 nodes has a height of 8.
Answer: ❌ IncorrectExplanation: The height calculation rule for a complete binary tree:
-
For a complete binary tree with height h, the number of nodes ranges from 2^(h-1) ≤ n ≤ 2^h – 1;
-
It can be deduced that h = ⌊log₂n⌋ + 1, when n=100, the height is 7, hence it is incorrect.
Question 4: In C++ STL, the pop operation of a stack (std::stack) returns the top element and removes it.
Answer: ❌ IncorrectExplanation: In C++ STL, the pop operation of std::stack only removes the top element without returning it; if you need to get the top element, you must first call the top() function (which returns a reference to the top element), and then call pop() to remove it.Therefore, the pop operation does not return the top element, which is incorrect.
Question 5: Circular queues use modulo operations to cycle through space.
Answer: ✅ CorrectExplanation: Circular queues use arrays for storage, and the rear pointer and front pointer utilize modulo operations (e.g., rear = (rear + 1) % capacity) to achieve space recycling, avoiding waste of space at the front of the array, hence it is correct.
Question 6: A binary tree with n nodes must have n-1 edges.
Answer: ✅ CorrectExplanation: A tree is an “acyclic connected graph”, and for any n nodes in a tree, the number of edges is fixed at n-1 (the minimum number of edges for a connected graph is n-1, and there are no extra edges for acyclic graphs).A binary tree is a special form of a tree, which also satisfies “n nodes n-1 edges”, hence it is correct.
Question 7: The following code implements the inorder traversal of a binary tree. Given the following binary tree, the inorder traversal result is 4 2 5 1 3 6.
Binary tree structure:
1
/ \
2 3
/ \ \
4 5 6 struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderIterative(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr || !st.empty()) {
while (curr) {
st.push(curr);
curr = curr->left;
}
curr = st.top();
st.pop();
cout << curr->val << " ";
curr = curr->right;
}
}Answer: ✅ CorrectExplanation: The code is the iterative implementation of inorder traversal of a binary tree (left → root → right), and the logic is correct:
-
First traverse the left subtree to the end, then pop the node to visit, and finally traverse the right subtree;
-
For the given binary tree, the inorder traversal order is 4 → 2 → 5 → 1 → 3 → 6, which is consistent with the result in the question, hence it is correct.
Question 8: The time complexity of the search operation implemented by the following code in a binary search tree is O(h), where h is the height of the tree.
TreeNode* searchBST(TreeNode* root, int val) {
while (root && root->val != val) {
root = (val < root->val) ? root->left : root->right;
}
return root;
}Answer: ✅ CorrectExplanation: The search process in a binary search tree: each comparison only moves to the left or right subtree, traversing at most h layers (the height of the tree).
-
Best case (balanced binary tree) h = log₂n, time complexity O(log n);
-
Worst case (skewed tree) h = n, time complexity O(n);
-
The overall time complexity is O(h), hence it is correct.
Question 9: The following code implements the dynamic programming version of the Fibonacci sequence calculation, and its time complexity is O(2ⁿ).
int fib_dp(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Answer: ❌ IncorrectExplanation: The dynamic programming version of Fibonacci calculation is implemented through iteration, traversing the range from 2 to n once, with O(1) operations performed in each iteration.The time complexity is O(n), not O(2ⁿ) (O(2ⁿ) is the time complexity of the ordinary recursive version), hence it is incorrect.
Question 10: There is a row of bananas, each banana has a different sweetness value. The little monkey wants to eat bananas but cannot eat adjacent bananas. The following code can find the combination of bananas that the little monkey can eat to maximize sweetness.
// bananas: sweetness of bananas
void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
vector<int> selected;
int i = bananas.size() - 1;
while (i >= 0) {
if (i == 0) {
selected.push_back(0);
break;
}
if (dp[i] == dp[i - 1]) {
i--;
} else {
selected.push_back(i);
i -= 2;
}
}
reverse(selected.begin(), selected.end());
cout << "The little monkey ate: ";
for (int idx : selected) {
cout << idx + 1 << " ";
}
cout << " bananas" << endl;
}
int main() {
vector<int> bananas = {1, 2, 3, 1}; // sweetness of each banana
vector<int> dp(bananas.size());
dp[0] = bananas[0];
dp[1] = max(bananas[0], bananas[1]);
for (int i = 2; i < bananas.size(); i++) {
dp[i] = max(bananas[i] + dp[i - 2], dp[i - 1]);
}
findSelectedBananas(bananas, dp);
return 0;
}Answer: ✅ CorrectExplanation: This question is a classic dynamic programming problem of “robbing houses”, and the core logic is correct:
-
dp[i] represents the maximum sweetness sum of the first i bananas, and the state transition equation is dp[i] = max(bananas[i] + dp[i – 2] (eat the i-th), dp[i – 1] (do not eat the i-th));
-
The backtracking process (findSelectedBananas): traverses from the back, if dp[i] == dp[i – 1], it means the i-th was not eaten, i–; otherwise, the i-th was eaten, i -= 2;
-
For the input {1, 2, 3, 1}, the dp array is [1, 2, 4, 4], backtracking gives selected indices 2 (sweetness 3) and 0 (sweetness 1), total sweetness 4, which is the optimal solution, hence it is correct.
3. Programming Questions (25 points each, total 50 points)
String Partitioning
// [GESP202509 Level 6] String Partitioning
/*
Problem-solving idea: dp
State representation: dp[i] represents the maximum value of partitioning the first i characters
State transition:
Enumerate the length len of the last non-repeating substring
dp[i] = max(dp[i], dp[j] + a[len]); (len <= 26 )
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long dp[N];
long long a[N];
char s[N];
int main() {
int n;
cin >> n;
cin >> s;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// Start calculating dp[i] from the 1st position
for (int i = 1; i <= n; i++) {
bool used[26] = {false}; // Create a new "letter usage record" each time
// Look back at most 26 characters from position i
for (int j = i - 1; j >= 0; j--) {
// If 26 characters have been seen, stop (because there can be at most 26 different letters)
if (i - j > 26) {
break;
}
char c = s[j]; // Current character
int idx = c - 'a'; // Convert to 0~25
if (used[idx]) { // Found a repeated letter! Cannot continue left
break;
}
used[idx] = true; // Mark this letter as used
int len = i - j; // Current substring length
dp[i] = max(dp[i], dp[j] + a[len]);
}
}
cout << dp[n] << endl;
return 0;
}
Goods Transportation
// [GESP202509 Level 6] Goods Transportation
/*
Problem-solving idea: Greedy + dfs
Analyzing the diagram, it can be seen that
The shortest distance traversing all nodes, except for the "longest path from root to leaf", all other edges need to be traversed back 2 times.
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 5;
int n;
vector<pair<int,int>> g[N];
ll ds[N], sumw;
void dfs(int u, int p, ll d) {
ds[u] = d;
for (auto [v, w] : g[u]) {
if (v == p) continue;
dfs(v, u, d + w);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int u, v, l; cin >> u >> v >> l;
g[u].push_back({v, l});
g[v].push_back({u, l});
sumw += l;
}
dfs(1, 0, 0);
ll mx = 0;
for (int i = 1; i <= n; i++) mx = max(mx, ds[i]);
cout << 2 * sumw - mx << "\n";
return 0;
}