#include <bits/stdc++.h> #include "incursion.h" #define ll int #define vi vector<ll> #define pp pair<ll, ll> #define vvi vector<vi> #define inf 1000000000 using namespace std; void dfs1(ll u, ll par,vvi& edges, vi& subTree, vi &parent){ parent[u] = par; for(ll v : edges[u]){ if(v == par) continue; dfs1(v, u, edges, subTree, parent); subTree[u] += subTree[v]; } return; } void move(ll u, ll v, vi& subTree){ ll y = subTree[v]; ll n = subTree.size(); subTree[v] = n; subTree[u] = n - y; } pp find(vvi edges){ ll n = edges.size(); vi subTree(n, 1); vi parent(n, -1); dfs1(0, 0, edges, subTree, parent); ll u = 0; while(true){ bool centroid = true; for(ll v : edges[u]){ if(subTree[v] > n / 2){ centroid = false; move(u, v, subTree); u = v; break; } } if(centroid) break; } ll secC = -1; ll mxSub = -1; for(ll v : edges[u]){ if(subTree[v] > mxSub){ mxSub = subTree[v]; secC = v; } } move(u, secC, subTree); bool centroid = true; for(ll v : edges[u]){ if(subTree[v] > n / 2){ centroid = false; move(u, v, subTree); break; } } move(secC, u, subTree); if(!centroid) secC = u; return {u, secC}; } void dfs2(ll u, vvi& edges, vi& was, vi& depth){ was[u] = 1; for(ll v : edges[u]){ if(was[v] == 1) continue; depth[v] = depth[u] + 1; dfs2(v, edges, was, depth); } return; } void dfs3(ll u, ll par, vvi& edges, vi& depth, vi &ans){ for(ll v : edges[u]){ if(v == par) continue; if(depth[v] < depth[u]) ans[v] = 1; else ans[v] = 0; dfs3(v, u, edges, depth, ans); } return; } std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) { ll n = F.size() + 1; safe--; vvi edges(n); for(pp x : F){ x.first--; x.second--; edges[x.first].push_back(x.second); edges[x.second].push_back(x.first); } pp cent = find(edges); vi depth(n, 0); vi was(n, 0); was[cent.first] = 1; was[cent.second] = 1; dfs2(cent.first, edges, was, depth); dfs2(cent.second, edges, was, depth); vi ans(n, 0); dfs3(safe, -1, edges, depth, ans); ans[safe] = 1; return ans; } void locate(std::vector<std::pair<int, int>> F, int curr, int t) { curr--; ll n = F.size() + 1; vvi edges(n); for(pp x : F){ x.first--; x.second--; edges[x.first].push_back(x.second); edges[x.second].push_back(x.first); } pp cent = find(edges); vi depth(n, 0); vi was(n, 0); was[cent.first] = 1; was[cent.second] = 1; dfs2(cent.first, edges, was, depth); dfs2(cent.second, edges, was, depth); vi parent(n, -1); vi centS(n, 1); dfs1(cent.first, cent.second, edges, centS, parent); if(cent.first != cent.second) dfs1(cent.second, cent.first, edges, centS, parent); vi cnt(n, 0); while(true){ cnt[curr]++; if(t == 0){ t = visit(parent[curr] + 1); curr = parent[curr]; }else if(t == 1){ ll mxS = -1; ll nextSon = -1; for(ll son : edges[curr]){ if(son == parent[curr]) continue; if(cnt[son] > 0) continue; if(centS[son] > mxS){ mxS = centS[son]; nextSon = son; } } if(nextSon == -1) break; t = visit(nextSon + 1); curr = nextSon; } } return; }