API tools faq
paste
yicongli

BZ1095

yicongli
Mar 10th, 2019
116
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.94 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=100005;
  17. const int INF=1e9;
  18.  
  19. int col[N];
  20. vector<int>G[N];
  21. int n;
  22.  
  23. namespace sp{
  24.    
  25.     int siz[N];
  26.     int dep[N];
  27.     int son[N];
  28.     int fa[N];
  29.    
  30.     void dfs1(int x,int f){
  31.         fa[x]=f;
  32.         siz[x]=1;
  33.         dep[x]=dep[f]+1;
  34.         for(int i=0;i<G[x].size();++i){
  35.             int v=G[x][i];
  36.             if(v==f)continue;
  37.             dfs1(v,x);
  38.             siz[x]+=siz[v];
  39.             if(siz[son[x]]<siz[v])son[x]=v;
  40.         }
  41.     }
  42.    
  43.     int top[N];
  44.    
  45.     void dfs2(int x,int t){
  46.         top[x]=t;
  47.         if(!son[x])return ;
  48.         dfs2(son[x],t);
  49.         for(int i=0;i<G[x].size();++i){
  50.             int v=G[x][i];
  51.             if(v==fa[x]||v==son[x])continue;
  52.             dfs2(v,v);
  53.         }
  54.     }
  55.    
  56.     inline int lca(int u,int v){
  57.         while(top[u]!=top[v]){
  58.             if(dep[top[u]]<dep[top[v]])swap(u,v);
  59.             u=fa[top[u]];
  60.         }
  61.         return dep[u]<dep[v]?u:v;
  62.     }
  63.    
  64.     inline int dist(int u,int v){
  65.         return dep[u]+dep[v]-2*dep[lca(u,v)];
  66.     }
  67. }
  68. using sp::dist;
  69.  
  70. namespace df{
  71.  
  72.     struct Heap{
  73.         multiset<int>A;
  74.        
  75.         inline void ins(int x){
  76.             A.insert(x);
  77.         }
  78.        
  79.         inline void del(int x){
  80.             A.erase(A.find(x));
  81.         }
  82.        
  83.         inline int max(){
  84.             return *A.rbegin();
  85.         }
  86.        
  87.         inline int sec(){
  88.             return *(++A.rbegin());
  89.         }
  90.        
  91.         inline Heap(){
  92.             A.insert(-INF);
  93.             A.insert(-INF);
  94.         }
  95.     }Ans,A[N],B[N];
  96.  
  97.     int root,SIZE;
  98.     int siz[N];
  99.     int s[N];
  100.     bool vis[N];
  101.    
  102.     void getroot(int x,int f){
  103.         siz[x]=1;
  104.         s[x]=0;
  105.         for(int i=0;i<G[x].size();++i){
  106.             int v=G[x][i];
  107.             if(v==f||vis[v])continue;
  108.             getroot(v,x);
  109.             siz[x]+=siz[v];
  110.             s[x]=max(s[x],siz[v]);
  111.         }
  112.         s[x]=max(s[x],SIZE-siz[x]);
  113.         if(s[x]<s[root])root=x;
  114.     }
  115.    
  116.     int fa[N];
  117.     vector<int>son[N];
  118.    
  119.     void build(int x,int size){
  120.         vis[x]=1;
  121.         for(int i=0;i<G[x].size();++i){
  122.             int v=G[x][i];
  123.             if(vis[v])continue;
  124.             s[root=0]=SIZE=(siz[x]<siz[v]?size-siz[x]:siz[v]);
  125.             getroot(v,0);
  126.             fa[root]=x;
  127.             son[x].push_back(root);
  128.             build(root,SIZE);
  129.         }
  130.     }
  131.    
  132.     inline void work(){
  133.         s[root=0]=SIZE=n;
  134.         getroot(1,0);
  135.         build(root,n);
  136.         for(int u=1;u<=n;++u){
  137.             for(int x=u,f;;x=f){
  138.                 f=fa[x];
  139.                 if(f)A[x].ins(dist(u,f));
  140.                 else break;
  141.             }
  142.         }
  143.         for(int i=1;i<=n;++i){
  144.             for(int j=0;j<son[i].size();++j){
  145.                 int x=son[i][j];
  146.                 B[i].ins(A[x].max());
  147.             }
  148.             B[i].ins(0);
  149.             Ans.ins(B[i].max()+B[i].sec());
  150.         }
  151.         int q;r(q);
  152.         int cnt=n;
  153.         while(q--){
  154.             char s[5];
  155.             scanf("%s",s);
  156.             if(s[0]=='G'){
  157.                 if(cnt==0)puts("-1");
  158.                 else if(cnt==1)puts("0");
  159.                 else printf("%d\n",Ans.max());
  160.             }
  161.             else {
  162.                 int u;r(u);
  163.                 if(col[u]){
  164.                     col[u]=0;
  165.                     ++cnt;
  166.                     int mx=B[u].max();
  167.                     int sc=B[u].sec();
  168.                     if(0>B[u].sec()){
  169.                         Ans.del(B[u].max()+B[u].sec());
  170.                         B[u].ins(0);
  171.                         Ans.ins(B[u].max()+B[u].sec());
  172.                     }
  173.                     else B[u].ins(0);
  174.                     for(int x=u,f;;x=f){
  175.                         f=fa[x];
  176.                         if(f){
  177. //                          Ans.del(B[f].max()+B[f].sec());
  178. //                          B[f].del(A[x].max());
  179. //                          A[x].ins(dist(u,f));
  180. //                          B[f].ins(A[x].max());
  181. //                          Ans.ins(B[f].max()+B[f].sec());
  182.                             int dis=dist(u,f);
  183.                             int mxa=A[x].max();
  184.                             if(dis>A[x].max()){
  185.                                 int mx=B[f].max();
  186.                                 int sc=B[f].sec();
  187.                                 if(dis>sc){
  188.                                     Ans.del(B[f].max()+B[f].sec());
  189.                                     B[f].del(A[x].max());
  190.                                     A[x].ins(dist(u,f));
  191.                                     B[f].ins(A[x].max());
  192.                                     Ans.ins(B[f].max()+B[f].sec());
  193.                                 }
  194.                                 else {
  195.                                     B[f].del(A[x].max());
  196.                                     A[x].ins(dist(u,f));
  197.                                     B[f].ins(A[x].max());
  198.                                 }
  199.                             }
  200.                             else A[x].ins(dist(u,f));
  201.                         }
  202.                         else break;
  203.                     }
  204.                 }
  205.                 else {
  206.                     col[u]=1;
  207.                     --cnt;
  208.                     int mx=B[u].max();
  209.                     int sc=B[u].sec();
  210.                     if(0>=B[u].sec()){
  211.                         Ans.del(B[u].max()+B[u].sec());
  212.                         B[u].del(0);
  213.                         Ans.ins(B[u].max()+B[u].sec());
  214.                     }
  215.                     else B[u].del(0);
  216.                     for(int x=u,f;;x=f){
  217.                         f=fa[x];
  218.                         if(f){
  219. //                          Ans.del(B[f].max()+B[f].sec());
  220. //                          B[f].del(A[x].max());
  221. //                          A[x].del(dist(u,f));
  222. //                          B[f].ins(A[x].max());
  223. //                          Ans.ins(B[f].max()+B[f].sec());int dis=dist(u,f);
  224.                             int dis=dist(u,f);
  225.                             int mxa=A[x].max();
  226.                             if(dis>=A[x].max()){
  227.                                 int mx=B[f].max();
  228.                                 int sc=B[f].sec();
  229.                                 if(dis>=sc){
  230.                                     Ans.del(B[f].max()+B[f].sec());
  231.                                     B[f].del(A[x].max());
  232.                                     A[x].del(dist(u,f));
  233.                                     B[f].ins(A[x].max());
  234.                                     Ans.ins(B[f].max()+B[f].sec());
  235.                                 }
  236.                                 else {
  237.                                     B[f].del(A[x].max());
  238.                                     A[x].del(dist(u,f));
  239.                                     B[f].ins(A[x].max());
  240.                                 }
  241.                             }
  242.                             else A[x].del(dist(u,f));
  243.                         }
  244.                         else break;
  245.                     }
  246.                 }
  247.             }
  248.         }
  249.     }
  250. }
  251.  
  252. int main(){
  253.     r(n);
  254.     for(int i=1;i<n;++i){
  255.         int u,v;r(u),r(v);
  256.         G[u].push_back(v);
  257.         G[v].push_back(u);
  258.     }
  259.     sp::dfs1(1,0);
  260.     sp::dfs2(1,1);
  261.     df::work();
  262.     return 0;
  263. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!