比赛的时候以为这是一道动态维护树的中心，看了题解发现自己想错了。公共祖先的题目确实是少

这次学习了一下set

发现有非常多使用简便的地方

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 111111#define iter set
            
             ::iteratorint par[N][20];int depth[N];int dis[N];int n,m;int p[N];int vis[N];int cnt;int dfn[N];vector
             
              
               >edge[N];set
               
                 ans;void dfs(int u,int fa){ dfn[++cnt]=u; p[u]=cnt; //printf("%d %d\n",u,fa); for(int i=1;i<18;i++){ //寻找他的十八辈祖宗 par[u][i]=par[par[u][i-1]][i-1]; } for(int i=0;i
                
                 depth[v]) swap(u,v); for(int k=0;k<18;k++){ if((depth[v]-depth[u])>>k&1){ v = par[v][k]; } } if(v==u) return u; for(int k=17;k>=0;k--){ if(par[u][k]!=par[v][k]){ u=par[u][k]; v=par[v][k]; } } return par[u][0];}int tot;int add(int u){ if (ans.empty()) return 0; int x, y; //寻找与u相邻的dfs序点 iter it = ans.lower_bound(p[u]); iter itx = it; itx--; if (it == ans.end() || it == ans.begin()) { it = ans.begin(); itx = ans.end(); itx--; } y = (*it); x = (*itx); y = dfn[y]; x = dfn[x]; return dis[u] - dis[lca(x, u)] - dis[lca(y, u)] + dis[lca(x, y)];}void init(){ for(int i=1;i<=n;i++){ edge[i].clear(); } memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(p,0,sizeof(p)); memset(par,0,sizeof(par)); memset(dis,0,sizeof(dis)); memset(depth,0,sizeof(depth)); cnt=0; ans.clear();}int main(){ int T; int cas = 0; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); init(); int x,y,z; for(int i=1;i