hdu 3078 Network

本文从WordPress迁移而来, 查看全部WordPress迁移文章

LCA

题意:单case,一棵无根树,输入点数和操作数,下面一行n个值代表每个点的权。下面n-1行是树边
操作分为

0 x w ,表示把点x的权改为w

k a b , 求出,从a到b的路径中,第k大的点权

这题,没什么太特别的地方,一开始写怕会超时,最后没有,就是直接按照题意来就可以了

对于修改操作就直接修改

对于查询第k个权的操作,先求出a,b的lca,然后将a到b路径上的点权都保存在一个数组中,然后降序排序,输出第k个元素即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define N 80010

int __pow[25];
int fa[N],val[N],p[N];
int node[2*N],first[N],dep[2*N],dp[2*N][25];
bool vis[N];
vector<int>e[N];

void dfs(int &index , int u ,int d , int par)
{
++index; vis[u] = true;
first[u] = index; node[index] = u; dep[index] = d; fa[u] = par;
for(int i=0; i<e[u].size(); i++)
if(!vis[e[u][i]])
{
dfs(index , e[u][i] , d+1 , u);
++index;
node[index] = u; dep[index] = d;
}
}

void ST(int n)
{
int K = (int)(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+__pow[j]-1 <= n ; i++)
{
int a = dp[i][j-1];
int b = dp[i+__pow[j-1]][j-1];
if(dep[a] < dep[b]) dp[i][j] = a;
else dp[i][j] = b;
}
}

int RMQ(int x ,int y)
{
int K = (int)(log((double)(y-x+1)) / log(2.0));
int a = dp[x][K];
int b = dp[y-__pow[K]+1][K];
if(dep[a] < dep[b]) return a;
else return b;
}

int LCA(int u ,int v)
{
int x = first[u];
int y = first[v];
if(x > y) swap(x,y);
int index = RMQ(x,y);
return node[index];
}

bool cmp(int a, int b)
{
return a > b;
}

void path(int &index , int s , int t)
{
while(s != t)
{
p[index++] = val[s];
s = fa[s];
}
p[index++] = val[t];
}

void solve(int kth , int u,int v)
{
int lca = LCA(u,v);
int tot = 0;
path(tot,u,lca);
path(tot,v,lca);
tot--;
if(kth > tot)
{
printf("invalid request!\n");
return ;
}
sort(p,p+tot,cmp);
printf("%d\n",p[kth-1]);
}

int main()
{
for(int i=0; i<25; i++) __pow[i] = 1 << i;

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

int tot = 0;
memset(vis,false,sizeof(vis));
dfs(tot,1,1,-1);

ST(tot);
while(q--)
{
int op;
scanf("%d",&op);
if(op == 0)
{
int x,w;
scanf("%d%d",&x,&w);
val[x] = w;
}
else
{
int u,v;
scanf("%d%d",&u,&v);
solve(op,u,v);
}
}
return 0;
}