F1. Game in Tree (Easy Version) time limit per test4 seconds memory limit per test256…
- User
F1. Game in Tree (Easy Version) time limit per test4 seconds memory limit per test256 megabytes This is the easy version of the problem. In this version, u=v . You can make hacks only if both versions of the problem are solved.
Alice and Bob are playing a fun game on a tree. This game is played on a tree with n vertices, numbered from 1 to n . Recall that a tree with n vertices is an undirected connected graph with n−1 edges.
Alice and Bob take turns, with Alice going first. Each player starts at some vertex.
On their turn, a player must move from the current vertex to a neighboring vertex that has not yet been visited by anyone. The first player who cannot make a move loses.
You are given two vertices u and v . Represent the simple path from vertex u to v as an array p1,p2,p3,…,pm , where p1=u , pm=v , and there is an edge between pi and pi+1 for all i (1≤i<m ).
You need to determine the winner of the game if Alice starts at vertex 1 and Bob starts at vertex pj for each j (where 1≤j≤m ).
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104 ). The description of the test cases follows.
The first line of each test case contains a single integer n (2≤n≤2⋅105 ) — the number of vertices in the tree.
Each of the following n−1 lines contains two integers a and b (1≤a,b≤n ), denoting an undirected edge between vertices a and b . It is guaranteed that these edges form a tree.
The last line of each test case contains two integers u and v (2≤u,v≤n , u=v ).
It is guaranteed that the path from u to v does not pass through vertex 1 .
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
Output For each test case, output m lines.
In the i -th line, print the winner of the game if Alice starts at vertex 1 and Bob starts at vertex pi . Print "Alice" (without quotes) if Alice wins, or "Bob" (without quotes) otherwise.
please analysis this problem and give me a effecitive solution using c++ and make lowercase variable and use simple variable name legth small please help me
- Assistant
To solve the problem where Alice and Bob are playing a game on a tree, we need to determine who will win based on their starting positions. In the easy version of the problem,
u = v, meaning Bob starts at nodeu. Alice starts at node1. The goal is to determine the winner based on the configuration of the tree.Key Insights:
-
Game Dynamics:
- Alice and Bob take turns to move from their respective starting nodes.
- A player loses if they cannot make a valid move on their turn.
-
Subtree Analysis:
- We need to calculate the size of the subtree rooted at Bob's starting node
u. - If the total number of nodes
nis greater than twice the size of Bob's subtree (2*t), Alice can win by having more available moves. - Otherwise, Bob wins because he can outlast Alice.
- We need to calculate the size of the subtree rooted at Bob's starting node
-
Implementation Steps:
- For each test case, read the tree structure and determine the size of the subtree rooted at node
u. - Compare
nwith2*t. Ifn > 2*t, Alice wins; otherwise, Bob wins.
- For each test case, read the tree structure and determine the size of the subtree rooted at node
Implementation in C++
Below is the C++ implementation that follows the above logic:
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to perform DFS and calculate subtree sizes int dfs(int u, int parent, vector<vector<int>> &adj, vector<int> &sz){ sz[u] = 1; for(auto &v: adj[u]){ if(v != parent){ sz[u] += dfs(v, u, adj, sz); } } return sz[u]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; vector<vector<int>> adj(n+1, vector<int>()); for(int i=0;i<n-1;i++){ int a,b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } int u, v; cin >> u >> v; // in easy version, u = v vector<int> sz(n+1, 0); dfs(1, -1, adj, sz); int t_size = sz[u]; if((ll)n > 2LL * t_size){ cout << "Alice\n"; } else{ cout << "Bob\n"; } } }Explanation:
-
DFS Function:
- The
dfsfunction calculates the size of each subtree in the tree. - It recursively counts the number of nodes in each subtree rooted at a given node.
- The
-
Main Function:
- For each test case, the tree is constructed using an adjacency list.
- The subtree size for node
uis calculated using DFS starting from node1. - Based on the comparison
n > 2*t_size, the program decides whether Alice or Bob will win and prints the result.
Example:
Consider a tree with
n = 3nodes andu = 2:1 | 2 | 3- Subtree size for node
2is2(nodes2and3). n = 3,2*t_size = 4.- Since
3 > 4is false, Bob wins.
This implementation ensures efficient processing of multiple test cases and handles large inputs within the given constraints.
-