Game on Leaves

Question

#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vc vector<char>
#define vii vector<vi>
#define mp make_pair
#define vpi vector< pair<int, int> >
#define take_input freopen("input.txt", "r", stdin)
#define give_output freopen("output.txt", "w", stdout)
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fi first
#define se second
#define mod 1000000007
#define min_pql priority_queue< int, vector<int>, greater<int> >

using namespace std;
using namespace std::chrono;

int32_t main(){
    fastIO;
    take_input;
    give_output;
    // write code
    int t; cin >> t;
    while(t--){
    	int n,x; cin >> n >> x;
		unordered_map<int, int> m;    	
    	for(int i=0; i<n-1; i++){
    		int a, b;
    		cin >> a >> b;
    		m[a]++; m[b]++;
    	}
    	vector<int> ind[n];
    	for(auto it=m.begin(); it!=m.end(); it++){
    		ind[it->se].pb(it->fi);
    	}
        int cnt=0;
    	for(int i=1; i<n; i++){
            if(!ind[i].empty()) cnt++;
            else continue;
    		sort(ind[i].begin(), ind[i].end());
    		auto it = lower_bound(ind[i].begin(), ind[i].end(), x);
    		if(it != ind[i].end() && *it == x){
    			if(cnt%2){
    				cout << "Ayush\n"; break;
    			}else{
    				cout << "Ashish\n"; break;
    			}
    		}
    	}
    }
}

I am ordering by degree and then looping over them to find the answer. But I am getting WA for third case. Can someone point out where I am wrong

I don’t think you require to iterate over the tree. You can calculate the degree of x and total nodes present in tree. As only leaf nodes can be removed, you cannot iterate over the degree of the vertices, example, 1 is connected to 2 and 2 is connected to 3, 1 has degree of 4 and 3 has degree of 5, now 2 has degree of 2 only, so you will remove this first which should not be the case, i guess i have understood your approach properly.

I was a bit confused reading your approach so I am explaining my once. While taking the input only I calculated the degree of each node. Now on first move I removed the nodes with degree 1 and then of degree 2 and so on. While removing nodes of a particular degree I am also checking for the required node.

Firstly, you are not considering how much nodes of some degree you have removed. Secondly, consider the following case,
8 2 ( 8 vertices and x=2)
1 2
2 3
3 4
3 5
1 6
1 7
1 8
Your code gives Ashish. But answer will be Ayush.