#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N = 4e5 + 5, NN = 4e5;
int n, m, Q;
vector < int > g[N];
int in[N], out[N];
int P[N][20];
int T;
void dfs (int k, int p){
in[k] = ++T;
P[k][0] = p;
for (int i = 1; i < 20; i++)
P[k][i] = P[P[k][i - 1]][i - 1];
for (int i = 0; i < g[k].size(); i++)
if (g[k][i] != p)
dfs (g[k][i], k);
out[k] = ++T;
}
int LCA (int u, int v){
if (u == 0 || v == 0)return u + v;
if (in[u] <= in[v] && out[v] <= out[u])
return u;
if (in[v] <= in[u] && out[u] <= out[v])
return v;
int I = u;
for (int i = 19; i >= 0; i--){
if (P[I][i] == 0)
continue;
if (in[P[I][i]] <= in[v] && out[v] <= out[P[I][i]])
continue;
I = P[I][i];
}
return P[I][0];
}
int a[N], S;
int le[N], ri[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>Q;
for (int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
g[u].pb (v);
g[v].pb (u);
}
dfs (1, 0);
for (int i = 1; i <= m; i++)
cin>>a[i];
S = sqrt(m - 1) + 1;
for (int i = 0; i < S * S; i += S){
le[i + 1] = a[i + 1];
for (int j = i + 2; j <= i + S; j++)
le[j] = LCA (a[j], le[j - 1]);
ri[i + S] = a[i + S];
for (int j = i + S - 1; j >= i + 1; j--)
ri[j] = LCA (a[j], ri[j + 1]);
}
while (Q--){
int t;
cin>>t;
if (t == 1){
int ind, x;
cin>>ind>>x;
a[ind] = x;
int i = ind - 1 - (ind - 1) % S;
le[i + 1] = a[i + 1];
for (int j = i + 2; j <= i + S; j++)
le[j] = LCA (a[j], le[j - 1]);
ri[i + S] = a[i + S];
for (int j = i + S - 1; j >= i + 1; j--)
ri[j] = LCA (a[j], ri[j + 1]);
continue;
}
int l, r, v;
cin>>l>>r>>v;
int p1 = -1, p2 = -1;
for (int L = 1; L <= S * S && p1 == -1; L += S){
if (L < l || r < L + S - 1)
continue;
int R = L - 1;
int X = 0;
while (R + S <= r && in[v] <= in[le[R + S]] && out[le[R + S]] <= out[v]){
R += S;
X = LCA (X, le[R]);
}
int x = L, y = R, xx, yy;
for (int i = 19; i >= 0; i--){
xx = x - (1<<i);
if (xx >= L - S && xx >= l && in[v] <= in[ri[xx]] && out[ri[xx]] <= out[v])
x = xx;
}
for (int i = 19; i >= 0; i--){
yy = y + (1<<i);
if (yy <= R + S && yy <= r && in[v] <= in[le[yy]] && out[le[yy]] <= out[v])
y = yy;
}
if (x < L)
X = LCA (X, ri[x]);
if (R < y)
X = LCA (X, le[y]);
if (X == v){
p1 = x;
p2 = y;
}
//cout<<x<<" "<<y<<" "<<X<<" "<<S<<" "<<L<<" "<<R<<" "<<le[R + S]<<endl;
L = R + 1;
}
cout<<p1<<" "<<p2<<endl;
}
return 0;
}
Compilation message
treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[k].size(); i++)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9720 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
9844 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9720 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
9844 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9720 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
9844 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9720 KB |
n=5 |
| 2 |
Incorrect |
8 ms |
9844 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
