#define MAXN 200050

const int MAXN = 200050;

//邻接表存树

struct edge{

   int to;   //边指向的顶点

   int next; //下一条边在链表中的位置

};

vector<edge> es;

int n,m,r,p,val[MAXN],u,v,x,y,c;

int head[MAXN];//记录每个节点的边的链表表头

int size[MAXN],fa[MAXN],dep[MAXN],son[MAXN];//节点重量，父节点，节点深度，重儿子

void addedge(int u,int v){

   static int edgeid=1; // 边的索引

   // es[edgeid].to=v;     // 记录目标顶点

   // es[edgeid].next=head[u];  //将新边记录在u点的边的链表头部

   es.push_back({v,head[u]});

   head[u]=edgeid++; //更新头部

}

void dfshld(int u,int f){

   size[u]=1;

   for(int i=head[u];i!=0;i=es[i].next){

       int v=es[i].to;

       if(v==f) continue;

       dep[v]=dep[u]+1;

       fa[v]=u;

       dfshld(v,u);

       size[u]+=size[v];

       if(size[v]>size[son[u]]){

           son[u]=v;

       }

   }

}

int top[MAXN],id[MAXN],rev[MAXN];

//链头，id：当前节点在序列中的编号，rev：当前这个编号对应的是第几个节点

int total=0;

void dfspos(int u,int t){

   top[u]=t; //将u的链头标记到t

   id[u]=++total; //当前节点是序列中的total节点

   rev[total]=u;  //当前total节点是u

   if(!son[u]) return ;

   dfspos(son[u],t); //沿着重儿子进行dfs

   for(int i=head[u];i!=0;i=es[i].next){ //将其他儿子也存放到线性序列中

       int v=es[i].to;

       if(v!=fa[u]&&v!=son[u]){

           dfspos(v,v);

       }

   }

}

int main(){

   cin>>n>>m>>r>>p;

   for(int i=1;i<=n;i++) cin>>val[i];

   for(int i=1;i<n;i++){

       cin>>u>>v;

       addedge(u,v);

       addedge(v,u);

   }

   dfshld(r,0);

   dfspos(r,r);

   输出top、id、rev三个数组，验证数据剖分是否正确。

   思考这个树形结构如何通过剖分后的数据进行线段树的构造。

   /*

   while(m--){

       cin>>c;

       switch(c){

           case 1:break;

           case 2:break;

           case 3:break;

           case 4:break;

       }

   }*/

   return 0;

}