hdu3078 Network--RMQ & LCA

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=3078​​

题意：给定n个点标号1到n，每个点一个权值，接下来n-1行u，v表示u和v两点连线，接下来k行查询，op，u，v，如果u为0，表示把点u权值改为v；若不是，求点u和点v连线路径上的所有点的权值第op小的值。题目保证不会有环的出现，且保证任何两点是可达的。

分析：这题正好是一个lca转rmq的模板题。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
#define N ((1<<12)+10)
using namespace std;

int n, k;
int index;
int cnt;
vector<int> vec[80005];
int father[80005];//父节点
int value[80005];//节点权值
int ans[80005];//待排序数组，保存第k元素
int node[2 * 80005];//保存第i次访问的节点
int first[80005];//i这个节点是第几次访问到的
int depth[2 * 80005];//第i次访问的节点的深度
int dp[2 * 80005][25];//dp[i][j]表示从第i次访问开始，连续2^j个访问内，哪次访问的节点深度最小
bool vis[80005];

bool cmp(int x, int y)
{
  return x > y;
}

void dfs(int u, int dep, int fa)
{
  

  index++;
  vis[u] = 1;
  first[u] = index;
  node[index] = u;
  depth[index] = dep;
  father[u] = fa;

  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i];
    if (!vis[v])
    {
      dfs(v, dep + 1, u);
      index++;
      node[index] = u;
      depth[index] = dep;
    }
  }
}


void ST(int n)
{
  int k = log((double)n) / log(2.0);
  for (int i = 1; i <= n; i++)
    dp[i][0] = i;

  for (int j = 1; j <= k; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
    {
      int a = dp[i][j - 1];
      int b = dp[i + (1 << (j - 1))][j - 1];
      if (depth[a] < depth[b])
        dp[i][j] = a;
      else
        dp[i][j] = b;
    }
}

int LCA(int u, int v)
{
  int i = first[u];
  int j = first[v];
  if (i > j)
    swap(i, j);

  int k = log(j - i + 1.0) / log(2.0);
  int a = dp[i][k];
  int b = dp[j - (1 << k) + 1][k];
  int x = (depth[a] < depth[b]) ? a : b;
  return node[x];
}

void path(int s,int t)
{
  while (s != t)
  {
    ans[cnt++] = value[s];
    s = father[s];
  }
  ans[cnt++] = value[t];
}


void solve(int kth,int u,int v)
{
  int lca = LCA(u, v);

  //cout << "lca是： " << lca << endl;

  cnt = 0;
  path(u, lca);
  path(v, lca);
  cnt--;//注意这里要减去，因为lca这个地方的权值被加进去两次
  if(cnt<kth)
    printf("invalid request!\n");
  else
  {
    sort(ans, ans + cnt, cmp);
    printf("%d\n", ans[kth - 1]);
  }
}

int main()
{
  int op, u, v;

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

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

  for (int i = 1; i < n; i++)
  {
    scanf("%d%d", &u, &v);
    vec[u].push_back(v);
    vec[v].push_back(u);
  }

  index = 0;
  dfs(1, 0, -1);
  ST(index);

  while (k--)
  {
    scanf("%d%d%d", &op, &u, &v);
    if (op == 0)
      value[u] = v;
    else
      solve(op, u, v);
  }
  return 0;
}