Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: Tree Stepping Game
- // Contest: HackerRank - FizzBuzz'22 Round1
- // URL: https://www.hackerrank.com/contests/fizzbuzz22-round1/challenges/tree-stepping-game-medium
- // Memory Limit: 512 MB
- // Time Limit: 4000 ms
- /*
- WINNERS NEVER QUIT AND QUITTERS NEVER WIN!!
- Falling down is an accident, Staying down is a choice.
- */
- #pragma GCC optimize("O3,unroll-loops")
- #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
- #include "bits/stdc++.h"
- /*#include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>*/
- using namespace std;
- //using namespace __gnu_pbds;
- typedef long long ll;
- typedef long double ld;
- typedef pair<ll,ll> pll;
- typedef vector<bool> vb;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- typedef vector<vi> vvi;
- typedef vector<vb> vvb;
- typedef vector<vll> vvll;
- typedef vector<pll> vpll;
- typedef vector<string> vs;
- typedef unordered_map<ll,ll> umll;
- template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
- /*template <typename num_t>
- using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;*/
- // find_by_order(k): iterator to the kth largest(0 indexed). order_of_key(k): no. of items < k
- #define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
- #define FOR3(i,a,b) for(long long i=a;i<b;i++)
- #define FOR4(i,a,b,step) for(long long i=a;i<b;i=i+step)
- #define REV3(i,a,b) for(long long i=a;i>=b;i--)
- #define REV4(i,a,b,step) for(long long i=a;i>=b;i=i-step)
- #define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3)(__VA_ARGS__)
- #define REV(...) GET_MACRO(__VA_ARGS__, REV4, REV3)(__VA_ARGS__)
- #define F first
- #define S second
- #define pb push_back
- #define ub upper_bound
- #define lb lower_bound
- #define all(v) v.begin(),v.end()
- #define rall(v) v.rbegin(),v.rend()
- #define tc ll tests;cin>>tests;while(tests--)
- #define io ios_base::sync_with_stdio(false);cin.tie(nullptr);
- #define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
- #define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
- #define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
- #define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
- #define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
- #define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
- #define pyes(CONDITION) cout << (CONDITION ? "YES" : "NO") << '\n';
- #define newl cout<<"\n"
- #define MOD 1000000007
- #define INF LLONG_MAX/2
- #define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
- #define m2(x) (int[]){(x forward<U>(b),0)...}
- m1(pr) { cout << forward<T>(a); m2(cout << " " <<); cout << "\n"; }
- m1(re) { cin >> forward<T>(a); m2(cin >>); }
- template <class ...Args>
- auto &readd(Args &...args) { return (cin >> ... >> args); }
- #define re(...) __VA_ARGS__; readd(__VA_ARGS__)
- const ll dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
- // const ll dx[8] = {-2,-1,1,2,2,1,-1,-2}, dy[8] = {1,2,2,1,-1,-2,-2,-1}; //knight moves
- // ************************DEBUG START********************************
- // #ifndef ONLINE_JUDGE
- // //#define cerr cout
- // #include "myprettyprint.hpp"
- // #else
- // #define dbg(...)
- // #endif
- // ************************DEBUG END**********************************
- constexpr ll pct(ll x) { return __builtin_popcountll(x); } // # of bits set
- constexpr ll bits(ll x) {return x == 0LL ? 0LL : 63LL-__builtin_clzll(x); } // floor(log2(x))
- constexpr ll p2(ll x) { return 1LL<<x; }
- constexpr ll msk2(ll x) { return p2(x)-1LL; }
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- struct centroid
- {
- const ll LOGN = 20;
- ll n;
- vvll g;
- vb vis; //denotes deleted nodes
- vll par, sz;
- void init(ll N)
- {
- n = N;
- g.resize(n);
- vis.resize(n, false);
- par.resize(n);
- sz.resize(n);
- }
- void edge(ll a, ll b)
- {
- g[a].push_back(b);
- g[b].push_back(a);
- }
- ll find_size(ll v, ll p = -1)
- {
- if (vis[v]) return 0;
- sz[v] = 1;
- for (ll x: g[v])
- {
- if (x == p) continue;
- sz[v] += find_size(x, v);
- }
- return sz[v];
- }
- ll find_centroid(ll v, ll p, ll n)
- {
- for (ll x: g[v])
- {
- if (x == p) continue;
- if (!vis[x] && sz[x] > n / 2)
- {
- return find_centroid(x, v, n);
- }
- }
- return v;
- }
- void init_centroid(ll v = 0, ll p = -1)
- {
- find_size(v);
- ll c = find_centroid(v, -1, sz[v]);
- vis[c] = true;
- par[c] = p;
- // process O(N) paths from centroid to all nodes in its subtree here
- // find centroids for the subtrees and make them children of current c.
- for (ll x: g[c])
- {
- if (!vis[x])
- {
- init_centroid(x, c);
- }
- }
- }
- };
- struct LCA
- {
- ll n, LOG, timer = 0;
- vvll g, up;
- vll tin, tout;
- vll lev;
- void init(ll x)
- {
- n=x;
- timer=0;
- LOG = ceil(log2(n));
- g.resize(n);
- up.resize(n, vll(LOG+1));
- tin.assign(n,0);
- tout.assign(n,0);
- lev.assign(n,0);
- }
- void edge(ll a, ll b)
- {
- g[a].push_back(b);
- g[b].push_back(a);
- }
- void dfs(ll u = 0, ll p = 0)
- {
- tin[u]=timer++;
- up[u][0] = p;
- FOR(i,1,LOG+1)
- {
- up[u][i] = up[up[u][i-1]][i-1];
- }
- for(auto v:g[u])
- {
- if(p==v) continue;
- lev[v] = lev[u] + 1;
- dfs(v,u);
- }
- tout[u]=timer++;
- }
- bool is_ancestor(ll u, ll v)
- {
- return tin[u]<=tin[v] && tout[u]>=tout[v];
- }
- ll lca(ll u, ll v)
- {
- if(is_ancestor(u,v)) return u;
- if(is_ancestor(v,u)) return v;
- REV(i,LOG,0)
- {
- if(!is_ancestor(up[u][i], v)) u = up[u][i];
- }
- return up[u][0];
- }
- ll dist(ll a, ll b)
- {
- ll l=lca(a,b);
- return lev[a]+lev[b]-2*lev[l];
- }
- ll lift(ll u, ll d)
- {
- while(d>0)
- {
- ll raise=log2(d);
- u=up[u][raise];
- d-=(1LL<<raise);
- }
- return u;
- }
- };
- vll best, mark;
- void paint(ll u, LCA &lca, centroid &cd)
- {
- ll v=u;
- while(v!=-1)
- {
- //best[v]=min(best[v], lca.dist(u,v));
- ll upd = lca.dist(u,v);
- if(upd<best[v])
- {
- mark[v] = u;
- best[v] = upd;
- }
- else if(upd==best[v] && mark[v]>u)
- {
- mark[v] = u;
- }
- v=cd.par[v];
- }
- }
- void test()
- {
- ll re(n);
- centroid cd;
- LCA lca;
- cd.init(n);
- lca.init(n);
- for(ll i=0;i<n-1;i++)
- {
- ll u, v;
- cin>>u>>v;
- u--;v--;
- cd.edge(u,v);
- lca.edge(u,v);
- }
- cd.init_centroid();
- lca.dfs();
- best.assign(n, INF);
- mark.assign(n, -1);
- tc
- {
- ll re(u);
- u--;
- if(best[u]==INF)
- {
- pr("NO");
- }
- else
- {
- pr("YES", mark[u]+1);
- }
- paint(u, lca, cd);
- }
- }
- int main()
- {
- io;
- ll tests=1;
- cin>>tests;
- while(tests--)
- {
- test();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement