Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///#include <stdio.h>
- ///#include <iostream>
- ///#include <cstring>
- ///#include <cmath>
- ///#include <algorithm>
- ///#include <string>
- ///#include <vector>
- ///#include <map>
- ///#include <set>
- ///#include <queue>
- ///#include <cstdlib>
- ///#include <limits>
- ///#include <iostream>
- ///#include <sstream>
- ///#include <unordered_set>
- ///#include <unordered_map>
- ///#include <random>
- #include <bits/stdc++.h>
- ///#include <bits/stdtr1c++.h>
- ///#include <ext/pb_ds/assoc_container.hpp>
- ///#include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- ///using namespace __gnu_pbds;
- #define MAX 200005
- #define EPS 1e-9
- #define ull unsigned long long
- #define ll long long
- #define inf INT_MAX
- #define pi acos(-1.0)
- #define vi vector<int>
- #define vl vector<long long>
- #define pii pair<int,int>
- #define pll pair<long long,long long>
- #define mp make_pair
- #define mem(a, v) memset(a, v, sizeof (a))
- #define mod 1000000007
- #define all(a) a.begin(),a.end()
- #define rall(a) a.rbegin(),a.rend()
- #define ff first
- #define ss second
- #define arsort(ar,n) sort(ar,ar+n);
- #define vsort(v) sort(v.begin(),v.end())
- #define vrev(v) reverse(v.begin(),v.end())
- #define arrev(ar,n) reverse(ar,ar+n)
- #define pb push_back
- #define popb pop_back
- #define booster() ios_base::sync_with_stdio(0); cin.tie(0);
- #define read(f) freopen(f, "r", stdin)
- #define scani(x) scanf("%d",&x)
- #define scanl(x) scanf("%I64d",&x)
- #define scand(x) scanf("%lf",&x)
- #define scans(x) scanf("%s",x)
- #define OUT(x) printf("%d\n",x)
- #define OUTS(x) printf("%d ",x)
- #define min3(a,b,c) min(a,min(b,c))
- #define max3(a,b,c) max(a,max(b,c))
- #define min4(a,b,c,d) min(min(a,b),min(c,d))
- #define max4(a,b,c,d) max(max(a,b),max(c,d))
- #define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
- #define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
- #define bitCheck(a,k) ((bool)(a&(1<<(k))))
- #define bitOff(a,k) (a&(~(1<<(k))))
- #define bitOn(a,k) (a|(1<<(k)))
- #define bitFlip(a,k) (a^(1<<(k)))
- #define POPCOUNT __builtin_popcount
- #define POPCOUNTLL __builtin_popcountll
- #define RIGHTMOST __builtin_ctzll
- #define LEFTMOST(x) (63-__builtin_clzll((x)))
- #define scani2(a,b) scani(a) , scani(b)
- #define scani3(a,b,c) scani(a), scani(b), scani(c)
- #define scani4(a,b,c,d) scani(a), scani(b), scani(c), scani(d)
- #define scani5(a,b,c,d,e) scani(a), scani(b), scani(c), scani(d) , scani(e)
- #define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- /*********************Ordered Multiset*************************/
- /*** Needs C++11 or C++14 ***/
- /// Treap supporting duplicating values in set
- /// Maximum value of treap * ADD must fit in long long
- /*
- struct Treap{ /// hash = 96814
- int len;
- const int ADD = 1000010;
- const int MAXVAL = 1000000010;
- tr1::unordered_map <long long, int> mp; /// Change to int if only int in treap
- tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> T;
- Treap(){
- len = 0;
- T.clear(), mp.clear();
- }
- inline void clear(){
- len = 0;
- T.clear(), mp.clear();
- }
- inline void insert(long long x){
- len++, x += MAXVAL;
- int c = mp[x]++;
- T.insert((x * ADD) + c);
- }
- inline void erase(long long x){
- x += MAXVAL;
- int c = mp[x];
- if (c){
- c--, mp[x]--, len--;
- T.erase((x * ADD) + c);
- }
- }
- /// 1-based index, returns the K'th element in the treap, -1 if none exists
- inline long long kth(int k){
- if (k < 1 || k > len) return -1;
- auto it = T.find_by_order(--k);
- return ((*it) / ADD) - MAXVAL;
- }
- /// Count of value < x in treap
- inline int count(long long x){
- x += MAXVAL;
- int c = mp[--x];
- return (T.order_of_key((x * ADD) + c));
- }
- /// Number of elements in treap
- inline int size(){
- return len;
- }
- };
- typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;///*X.find_by_order();X.order_of_key();
- template <class T> inline bool isLeap(T y) {return (y % 400 == 0) || (y % 100 ? y % 4 == 0 : false); }*/
- template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % (b))); }
- template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b)) * (b)); }
- template <class T> inline T BigMod(T Base,T power,T M=mod){if(power==0)return 1;if(power&1)return ((Base%M)*(BigMod(Base,power-1,M)%M))%M;else{T y=BigMod(Base,power/2,M)%M;return (y*y)%M;}}
- template <class T> inline T ModInv (T A,T M = mod){return BigMod(A,M-2,M);}
- int fx[] = {-1,+0,+1,+0,+1,+1,-1,-1,+0};
- int fy[] = {+0,-1,+0,+1,+1,-1,+1,-1,+0};
- int day[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
- /*********************** let the play begin() ***********************************/
- int par[MAX],lev[MAX],table[MAX][25];vi v[MAX],tree[MAX];int root;int Subtree[MAX],del[MAX],n,totalnode,parent[MAX],level[MAX],res;multiset<int >ans[MAX];
- void dfs1(int s,int p,int l)
- {
- par[s] = p;
- lev[s] = l;
- for(auto it : v[s])
- {
- if(it==p)continue;
- dfs1(it,s,l+1);
- }
- }
- void lca_init()
- {
- for(int i = 1;i<=n;i++)
- {
- table[i][0] = par[i];
- }
- for(int i = 1;i<=n;i++)
- {
- for(int j = 1;(1<<j)<=n;j++)
- {
- if(table[i][j-1]!=-1)
- {
- table[i][j] = table[table[i][j-1]][j-1];
- }
- }
- }
- }
- int lca_query(int uu,int vv)
- {
- if(lev[vv]<lev[uu])swap(uu,vv);
- int log = 1;
- while((1<<log)<lev[vv])log++;
- for(int i = log;i>=0;i--)
- {
- if(lev[vv] - (1<<i)>=lev[uu])
- {
- vv = table[vv][i];
- }
- }
- if(uu==vv)return uu;
- for(int i = log;i>=0;i--)
- {
- if(table[vv][i]!=-1&&table[vv][i]!=table[uu][i])
- {
- vv = table[vv][i];
- uu = table[uu][i];
- }
- }
- return par[uu];
- }
- void dfs2(int s,int p)
- {
- Subtree[s] = 1;
- totalnode++;
- for(auto it : v[s])
- {
- if(it==p||del[it])continue;
- dfs2(it,s);
- Subtree[s]+=Subtree[it];
- }
- }
- int Getcenter(int s,int p)
- {
- for(auto it : v[s])
- {
- if(it==p||del[it])continue;
- if(Subtree[it]>totalnode/2)return Getcenter(it,s);
- }
- return s;
- }
- void Decompose(int x,int p)
- {
- totalnode = 0;
- dfs2(x,p);
- int s = Getcenter(x,p);
- del[s] = 1;
- if(p>0)
- {
- tree[s].pb(p);
- tree[p].pb(s);
- }
- else root = s;
- for(auto it : v[s])
- {
- if(it==p||del[it])continue;
- Decompose(it,s);
- }
- }
- int distance(int uu,int vv){return lev[uu]+lev[vv] - 2* lev[lca_query(uu,vv)];}
- int colour[MAX];
- void change0(int u,int p)
- {
- if(u==-1)return ;
- ///cout<<u<<" pokran "<<endl;
- ans[u].insert(distance(u,p));
- change0(parent[u],p);
- }
- void change1(int u,int p)
- {
- if(u==-1)return ;
- ans[u].erase(ans[u].find(distance(u,p)));
- change1(parent[u],p);
- }
- void query(int u,int p)
- {
- if(u==-1)return ;
- ///cout<<distance(u,p)<<" klkl"<<u<<" "<<p<<endl;
- res = min(res,*ans[u].begin()+distance(u,p));
- query(parent[u],p);
- }
- void dfs3(int s,int p,int l = 0)
- {
- parent[s] = p;
- level[s] = l;
- for(auto it : tree[s])
- {
- if(it==p)continue;
- dfs3(it,s,l+1);
- }
- }
- int main()
- {
- booster()
- ///read("input.txt");
- cin>>n;
- for(int i = 0;i<n-1;i++)
- {
- int a,b;
- cin>>a>>b;
- v[a].pb(b);
- v[b].pb(a);
- }
- dfs1(1,-1,0);
- lca_init();
- ///cout<<x<<" center"<<endl;
- Decompose(1,-1);
- ///cout<<"root of the centroid is "<<root<<endl;
- ///for(int i = 1;i<=n;i++)for(auto it : tree[i])cout<<i<<" "<<it<<endl;
- dfs3(root,-1);
- /// for(int i = 1;i<=n;i++)cout<<parent[i]<<" lplpl "<<endl;
- int q;
- cin>>q;
- for(int i = 1;i<=n;i++)colour[i] = 1,ans[i].insert(inf/10);
- while(q--)
- {
- int ch,vv;
- cin>>ch>>vv;
- res = inf/10;
- if(ch==0)
- {
- if(colour[vv]==0)
- {
- colour[vv] = 1;
- change1(vv,vv);
- }
- else
- {
- colour[vv] = 0;
- change0(vv,vv);
- }
- }
- else
- {
- query(vv,vv);
- if(res>=inf/10)res = -1;
- cout<<res<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement