hdu 3078 Network (LCA)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年07月31日 星期一 01时12分54秒
  4File Name :3078.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define PB push_back
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28
 29using namespace std;
 30const double eps = 1E-8;
 31const int dx4[4]={1,0,0,-1};
 32const int dy4[4]={0,-1,1,0};
 33const int inf = 0x3f3f3f3f;
 34const int N=8E4+7;
 35int n,q;
 36int val[N];
 37vector < pi > edge[N];
 38int in[N];
 39int E[2*N],R[2*N],dis[N],depth[2*N];
 40int p;
 41int fa[N];
 42int dp[2*N][20];
 43void dfs( int u,int dep,int d,int pre)
 44{
 45
 46    //  cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl;
 47    fa[u] = pre;
 48    p++;
 49    E[p] = u;
 50    depth[p] = dep;
 51    R[u] = p ;
 52    dis[u] = d;
 53
 54
 55    int siz = edge[u].size();
 56    for ( int i = 0 ; i < siz ; i++)
 57    {
 58        int v = edge[u][i].fst;
 59        if (v==pre) continue;
 60        dfs(v,dep+1,d+edge[u][i].sec,u);
 61
 62        p++;
 63        E[p] = u;
 64        depth[p] = dep;
 65    }
 66}
 67
 68
 69
 70int _min( int l,int r)
 71{
 72    if (depth[l]<depth[r]) return l;
 73    return r;
 74}
 75void rmq_init()
 76{
 77    for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;
 78
 79    for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
 80        for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
 81            dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
 82}
 83
 84int rmq_min( int l,int r)
 85{
 86    if (l>r) swap(l,r);
 87    int k = 0 ;
 88    while (1<<(k+1)<=r-l+1) k++;
 89    return _min(dp[l][k],dp[r-(1<<k)+1][k]);
 90}
 91int D(int u,int v) //计算u,v点的距离
 92{
 93    int LCA = E[rmq_min(R[u],R[v])];
 94    int res = dis[u] + dis[v] - 2*dis[LCA];
 95    return res;
 96}
 97void get_path(vector<int> &v,int s,int t)
 98{
 99    while (s!=t)
100    {
101	v.PB(val[s]);
102	s = fa[s];
103    }
104}
105bool cmp(int a ,int b){return a>b;}
106void solve(int k,int u,int v)
107{
108    int LCA = E[rmq_min(R[u],R[v])];
109    vector<int>path;
110    get_path(path,u,LCA);
111    get_path(path,v,LCA);
112    path.PB(val[LCA]);
113    sort(path.begin(),path.end(),cmp);
114    int siz = path.size();
115 //   for ( int i = 0 ; i < siz ; i++) printf("%d ",path[i]);
116 //   printf("\n");
117    if (k>siz)
118    {
119	puts("invalid request!");
120	return;
121    }
122    printf("%d\n",path[k-1]);
123
124}
125int main()
126{
127	#ifndef  ONLINE_JUDGE 
128	freopen("./in.txt","r",stdin);
129  #endif
130	while (~scanf("%d%d",&n,&q))
131	{
132	    ms(val,0);
133	    for ( int i = 1 ;i <= n ; i++) scanf("%d",&val[i]);
134	    for ( int i = 1 ; i <= n-1 ; i++)
135	    {
136		int u,v;
137		scanf("%d%d",&u,&v);
138		edge[u].PB(MP(v,1));
139		edge[v].PB(MP(u,1));
140	    }
141	    p = 0 ;
142	    dfs(1,0,0,-1);
143	    rmq_init();
144	    while (q--)
145	    {
146		int k,u,v;
147		scanf("%d%d%d",&k,&u,&v);
148		if (k==0)
149		{
150		    val[u] = v;
151		}
152		else 
153		{
154		    solve(k,u,v);
155		}
156	    }
157	}
158
159
160  #ifndef ONLINE_JUDGE  
161  fclose(stdin);
162  #endif
163    return 0;
164}