Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 100007
- #define INF 1e18+7
- #define LOG 50
- using namespace std;
- vector<int> graph[MAX];
- struct Centroid {
- int vis[MAX], siz[MAX], root;
- int parent[MAX], layer[MAX];
- int state[MAX];
- vector<int> tree[MAX];
- void init(){
- for(int i = 0; i < MAX; i++){
- vis[i] = siz[i] = layer[i] = parent[i] = state[i] = 0;
- tree[i].clear();
- }
- }
- int getCent(int u, int n, int p = 0){
- for(int i = 0; i < graph[u].size(); i++){
- int v = graph[u][i];
- if(!vis[v] && v != p && siz[v] > n/2) return getCent(v, n, u);
- }
- return u;
- }
- int find(int u, int p = 0){
- siz[u] = 1;
- for(int i = 0; i < graph[u].size(); i++){
- int v = graph[u][i];
- if(v != p && !vis[v]){
- find(v, u);
- siz[u] += siz[v];
- }
- }
- return p? 0: getCent(u, siz[u]);
- }
- void build(int u = 0){
- if(u == 0){
- u = root = find(1);
- vis[u] = 1;
- layer[u] = 1;
- }
- for(int i = 0; i < graph[u].size(); i++){
- int v = graph[u][i];
- if(!vis[v]){
- int x = find(v);
- vis[x] = 1;
- layer[x] = layer[u] + 1;
- parent[x] = u;
- tree[u].push_back(x);
- tree[x].push_back(u);
- build(x);
- }
- }
- }
- vector<int> operator[](int i)const{
- return tree[i];
- }
- } c;
- int vis[MAX], parent[LOG][MAX];
- long long h[MAX];
- void dfs(int no){
- vis[no] = true;
- for(int i = 0; i < graph[no].size(); i++){
- int v = graph[no][i];
- if(!vis[v]){
- h[v] = h[no] + 1;
- parent[0][v] = no;
- dfs(v);
- }
- }
- }
- void build(int no){
- parent[0][no] = no;
- for(int i = 1; (1 << i) <= MAX; i++){
- for(int j = 1; j <= MAX; j++){
- parent[i][j] = parent[i-1][parent[i-1][j]];
- }
- }
- }
- int lca(int u, int v){
- if(h[u] < h[v]) swap(u, v);
- int lg;
- for(lg = 1; (1 << lg) <= h[u]; lg++);
- lg--;
- for(int i = lg; i >= 0; i--){
- if(h[parent[i][u]] >= h[v]) u = parent[i][u];
- }
- if(u == v) return u;
- for(int i = lg; i >= 0; i--){
- if(parent[i][u] != parent[i][v]){
- u = parent[i][u];
- v = parent[i][v];
- }
- }
- return parent[0][u];
- }
- multiset<long long> dists[MAX];
- void update(int no){
- //cout << "Adicionando...\n";
- int neigh = c.parent[no];
- dists[no].insert(0);
- while(neigh != 0){
- //cout << "parent -> " << neigh;
- int ancestor = lca(no, neigh);
- long long dist = h[no]+h[neigh]-2*h[ancestor];
- //cout << " a distancia " << dist << endl;
- //cout << "o parente de " << no << " e " << neigh << " is " << ancestor << endl;
- dists[neigh].insert(dist);
- neigh = c.parent[neigh];
- }
- }
- void rmv(int no){
- //cout << "removendo...\n";
- int neigh = c.parent[no];
- dists[no].erase(0);
- while(neigh != 0){
- //cout << "parent -> " << neigh;
- int ancestor = lca(no, neigh);
- long long dist = h[no]+h[neigh]-2*h[ancestor];
- //cout << " a distancia " << dist << endl;
- //cout << "o parente de " << no << " e " << neigh << " is " << ancestor << endl;
- dists[neigh].erase(dist);
- neigh = c.parent[neigh];
- }
- }
- long long solve(int no){
- int neigh = c.parent[no];
- multiset<long long>::iterator it = dists[no].begin();
- long long ans = *it;
- while(neigh != 0){
- it = dists[neigh].begin();
- int ancestor = lca(no, neigh);
- long long dist = *it + (h[no]+h[neigh]-2*h[ancestor]);
- ans = min(ans, dist);
- neigh = c.parent[neigh];
- }
- return ans;
- }
- int main(){
- c.init();
- int n; scanf("%d", &n);
- for(int i = 0; i < n-1; i++){
- int a, b; scanf("%d %d", &a, &b);
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- c.build();
- dfs(1);
- build(1);
- for(int i = 1; i <= n; i++) dists[i].insert(INF);
- int q; scanf("%d", &q);
- while(q--){
- int type, no; scanf("%d %d", &type, &no);
- if(type == 0){
- c.state[no] ^= 1;
- if(c.state[no]) update(no);
- else rmv(no);
- }else {
- long long resp = solve(no);
- printf("%lld\n", resp == INF? -1: resp);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement