hdu3078 伪LCA……

题意：有 n 点的一颗树，每个节点有格子的权值，现在有两种操作，修改一个点的权值，或者求两点之间的路径上的第 k 大的权值。

其实看到这个题，就在 YY 各种做法，询问后得到貌似可能是关于主席树、树链剖分等高端数据结构做的，但事实上，大概是出题人也并不想出难题，只是为了练练手所以……直接把每个问题路径上的点权保存在数组中 sort 一下就行了。然后树上路径就果断是LCA了，不过这里LCA也就不用倍增了，直接一步一步向上爬然后顺便加数组就行了。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 const int maxn=8e4+;

 const int maxm=maxn*;

 int fa[maxn],dep[maxn];

 int head[maxn],point[maxm],nxt[maxm],size;

 int n,num[maxn],que[maxn],cnt;

 void init(){

     size=;

     memset(head,-,sizeof(head));

 }

 void add(int a,int b){

     point[size]=b;

     nxt[size]=head[a];

     head[a]=size++;

     point[size]=a;

     nxt[size]=head[b];

     head[b]=size++;

 }

 void Dfs(int s,int pre){

     fa[s]=pre;

     dep[s]=dep[pre]+;

     for(int i=head[s];~i;i=nxt[i]){

         int j=point[i];

         if(j==pre)continue;

         Dfs(j,s);

     }

 }

 void Pre(){

     dep[]=;

     Dfs(,-);

 }

 void Lca(int u,int v){

     cnt=;

     if(dep[u]>dep[v])swap(u,v);

     while(dep[u]<dep[v]){

         que[++cnt]=num[v];

         v=fa[v];

     }

     while(u!=v){

         que[++cnt]=num[u];

         u=fa[u];

         que[++cnt]=num[v];

         v=fa[v];

     }

     que[++cnt]=num[u];

 }

 int main(){

     int m;

     scanf("%d%d",&n,&m);

     init();

     for(int i=;i<=n;++i)scanf("%d",&num[i]);

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

         int a,b;

         scanf("%d%d",&a,&b);

         add(a,b);

     }

     Pre();

     while(m--){

         int f,a,b;

         scanf("%d%d%d",&f,&a,&b);

         if(f){

             Lca(a,b);

             if(cnt<f)printf("invalid request!\n");

             else{

                 sort(que+,que+cnt+);

                 printf("%d\n",que[cnt-f+]);

             }

         }

         else num[a]=b;

     }

 }

巴特西

hdu3078 伪LCA……

最新文章

热门文章