2022_Round_F-Water_Container_System.cpp

/*
    written by Pankaj Kumar.
    country:-INDIA
*/
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define speed    \
    cin.tie(0);  \
    cout.tie(0); \
    ios_base::sync_with_stdio(0);
/*  Abbrevations  */
#define ff first
#define ss second
#define mp make_pair
#define line cout << endl;
#define pb push_back
// loops
#define forin(arr, n)          \
    for (ll i = 0; i < n; i++) \
        cin >> arr[i];
// Some print
#define no cout << "NO" << endl;
#define yes cout << "YES" << endl;
// sort
#define all(V) (V).begin(), (V).end()
#define srt(V) sort(all(V))
#define srtGreat(V) sort(all(V), greater<ll>())
// some extra
#define printv(v)                         \
    for (ll i = 0; i < ll(v.size()); i++) \
    {                                     \
        cout << v[i] << " ";              \
    }                                     \
    line;
#define precision(x) cout << fixed << setprecision(x);
#define sz(V) ll(V.size())
// function
ll power(ll x, ll y, ll mod)
{
    ll res = 1;
    // x=x%mod;
    while (y > 0)
    {
        if (y % 2 == 1)
        {
            res *= x;
            // res=res%mod;
        }
        y /= 2;
        x *= x; // x=x%mod;
    }
    return res;
}
ll str_to_num(string s)
{
    stringstream pk(s);
    ll num;
    pk >> num;
    return num;
}
string num_to_str(ll num)
{
    return to_string(num);
}
// datatype definination
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
/* ascii value
A=65,Z=90,a=97,z=122
*/

/* Some syntax
//Syntax to create a min heap for priority queue
//priority_queue <int, vector<int>, greater<int>>pq;
*/
/*  --------------------MAIN PROGRAM----------------------------*/
// to run ctrl+b
const ll INF = 1e18;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
// Techniques :
// divide into cases, brute force, pattern finding
// sort, greedy, binary search, two pointer
// transform into graph

// Experience :
// Cp is nothing but only observation and mathematics.

ll solve()
{
    int n, q;
    cin >> n >> q;


    vector<vector<int>> v(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a - 1].pb(b - 1);
        v[b - 1].pb(a - 1);
    }


    
    vector<int> height(n, 0);
    vector<bool> visited(n, false);
    queue<int> q1;
    q1.push(0);
    visited[0] = true;
    height[0] = 0;
    while (!q1.empty())
    {
        int root = q1.front();
        q1.pop();
        for (auto x : v[root])
        {
            if (!visited[x])
            {
                visited[x] = true;
                height[x] = height[root] + 1;
                q1.push(x);
            }
        }
    }

    map<int,int> m;
    for(auto x:height){
        m[x]++;
    }

    vector<int> checkpoint;
    int sm = 0;
    for (auto it : m)
    {
        sm += it.second;
        checkpoint.push_back((sm));
    }
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
    }
    checkpoint.push_back(n);
    cout << *--upper_bound(all(checkpoint), q) << '\n';
    return 0;
}
int main()
{
    speed;
    /* #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif */
    ll TestCase = 1;
    cin >> TestCase;
    for (ll i = 1; i <= TestCase; i++)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}
/* -----------------END OF PROGRAM --------------------*/
/*
 * stuff you should look before submission
 * constraint and time limit
 * int overflow
 * special test case (n=0||n=1||n=2)
 * don't get stuck on one approach if you get wrong answer
 */