hdu 3078 Network (LCA)

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=8E4+7;
 7int n,q;
 8int val[N];
 9vector < pi > edge[N];
10int in[N];
11int E[2*N],R[2*N],dis[N],depth[2*N];
12int p;
13int fa[N];
14int dp[2*N][20];
15void dfs( int u,int dep,int d,int pre)
16{

1    //  cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl;
2    fa[u] = pre;
3    p++;
4    E[p] = u;
5    depth[p] = dep;
6    R[u] = p ;
7    dis[u] = d;

1    int siz = edge[u].size();
2    for ( int i = 0 ; i < siz ; i++)
3    {
4        int v = edge[u][i].fst;
5        if (v==pre) continue;
6        dfs(v,dep+1,d+edge[u][i].sec,u);

1        p++;
2        E[p] = u;
3        depth[p] = dep;
4    }
5}

1int _min( int l,int r)
2{
3    if (depth[l]<depth[r]) return l;
4    return r;
5}
6void rmq_init()
7{
8    for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;

1    for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
2        for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
3            dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
4}

 1int rmq_min( int l,int r)
 2{
 3    if (l>r) swap(l,r);
 4    int k = 0 ;
 5    while (1<<(k+1)<=r-l+1) k++;
 6    return _min(dp[l][k],dp[r-(1<<k)+1][k]);
 7}
 8int D(int u,int v) //计算u,v点的距离
 9{
10    int LCA = E[rmq_min(R[u],R[v])];
11    int res = dis[u] + dis[v] - 2*dis[LCA];
12    return res;
13}
14void get_path(vector<int> &v,int s,int t)
15{
16    while (s!=t)
17    {
18	v.PB(val[s]);
19	s = fa[s];
20    }
21}
22bool cmp(int a ,int b){return a>b;}
23void solve(int k,int u,int v)
24{
25    int LCA = E[rmq_min(R[u],R[v])];
26    vector<int>path;
27    get_path(path,u,LCA);
28    get_path(path,v,LCA);
29    path.PB(val[LCA]);
30    sort(path.begin(),path.end(),cmp);
31    int siz = path.size();
32 //   for ( int i = 0 ; i < siz ; i++) printf("%d ",path[i]);
33 //   printf("\n");
34    if (k>siz)
35    {
36	puts("invalid request!");
37	return;
38    }
39    printf("%d\n",path[k-1]);

 1}
 2int main()
 3{
 4	#ifndef  ONLINE_JUDGE 
 5	freopen("./in.txt","r",stdin);
 6  #endif
 7	while (~scanf("%d%d",&n,&q))
 8	{
 9	    ms(val,0);
10	    for ( int i = 1 ;i <= n ; i++) scanf("%d",&val[i]);
11	    for ( int i = 1 ; i <= n-1 ; i++)
12	    {
13		int u,v;
14		scanf("%d%d",&u,&v);
15		edge[u].PB(MP(v,1));
16		edge[v].PB(MP(u,1));
17	    }
18	    p = 0 ;
19	    dfs(1,0,0,-1);
20	    rmq_init();
21	    while (q--)
22	    {
23		int k,u,v;
24		scanf("%d%d%d",&k,&u,&v);
25		if (k==0)
26		{
27		    val[u] = v;
28		}
29		else 
30		{
31		    solve(k,u,v);
32		}
33	    }
34	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}