#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,q;
vector<ll> g[maxN];
ll P[maxN][19],h[maxN];
void dfs(ll u=1,ll p=1)
{
P[u][0]=p;
for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
for(int v:g[u])
{
if(v!=p)
{
h[v]=h[u]+1;
dfs(v,u);
}
}
}
ll a[maxN];
set<int> s[maxN];
ll lca(ll u,ll v)
{
if(h[u]<h[v]) swap(u,v);
for(int i=18;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
if(u==v) return u;
for(int i=18;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
return P[u][0];
}
set<int> ss[maxN];
void solve()
{
cin >> n >> m >> q;
for(int i=1;i<n;i++)
{
ll u,v;
cin >> u >> v ;
g[u].pb(v);
g[v].pb(u);
}
dfs();
for(int i=1;i<=m;i++)
{
cin >> a[i];
if(i>1)
{
s[lca(a[i],a[i-1])].insert(i);
}
ss[a[i]].insert(i);
}
for(int tt=1;tt<=q;tt++)
{
ll t;
cin >> t;
if(t==1)
{
ll i,val;
cin >> i >> val;
ss[a[i]].erase(i);
ss[val].insert(i);
if(i>1)
{
s[lca(a[i],a[i-1])].erase(i);
s[lca(val,a[i-1])].insert(i);
}
if(i<n)
{
s[lca(a[i],a[i+1])].erase(i+1);
s[lca(val,a[i+1])].insert(i+1);
}
a[i]=val;
}
else
{
ll l,r,v;
cin >> l >> r >> v;
auto cc=s[v].upper_bound(l);
if(cc!=s[v].end()&&*cc<=r)
{
cout << *cc-1<<' '<<*cc<<'\n';
}
else
{
cc=ss[v].lower_bound(l);
if(cc!=ss[v].end()&&*cc<=r)
{
cout << *cc<<' '<<*cc<<'\n';
}
else cout << -1 <<' '<<-1<<'\n';
}
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
n=5 |
2 |
Correct |
12 ms |
23764 KB |
n=100 |
3 |
Correct |
13 ms |
23804 KB |
n=100 |
4 |
Correct |
12 ms |
23816 KB |
n=100 |
5 |
Correct |
12 ms |
23812 KB |
n=100 |
6 |
Correct |
11 ms |
23820 KB |
n=100 |
7 |
Correct |
13 ms |
23764 KB |
n=100 |
8 |
Correct |
12 ms |
23856 KB |
n=100 |
9 |
Correct |
14 ms |
23808 KB |
n=100 |
10 |
Correct |
13 ms |
23812 KB |
n=100 |
11 |
Correct |
12 ms |
23764 KB |
n=100 |
12 |
Correct |
15 ms |
23764 KB |
n=100 |
13 |
Correct |
13 ms |
23820 KB |
n=100 |
14 |
Correct |
12 ms |
23816 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23764 KB |
n=100 |
18 |
Correct |
12 ms |
23764 KB |
n=100 |
19 |
Correct |
12 ms |
23816 KB |
n=100 |
20 |
Correct |
12 ms |
23764 KB |
n=100 |
21 |
Correct |
12 ms |
23844 KB |
n=100 |
22 |
Correct |
12 ms |
23804 KB |
n=100 |
23 |
Correct |
12 ms |
23840 KB |
n=100 |
24 |
Correct |
14 ms |
23796 KB |
n=100 |
25 |
Correct |
12 ms |
23764 KB |
n=100 |
26 |
Correct |
13 ms |
23764 KB |
n=12 |
27 |
Correct |
13 ms |
23784 KB |
n=100 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
n=5 |
2 |
Correct |
12 ms |
23764 KB |
n=100 |
3 |
Correct |
13 ms |
23804 KB |
n=100 |
4 |
Correct |
12 ms |
23816 KB |
n=100 |
5 |
Correct |
12 ms |
23812 KB |
n=100 |
6 |
Correct |
11 ms |
23820 KB |
n=100 |
7 |
Correct |
13 ms |
23764 KB |
n=100 |
8 |
Correct |
12 ms |
23856 KB |
n=100 |
9 |
Correct |
14 ms |
23808 KB |
n=100 |
10 |
Correct |
13 ms |
23812 KB |
n=100 |
11 |
Correct |
12 ms |
23764 KB |
n=100 |
12 |
Correct |
15 ms |
23764 KB |
n=100 |
13 |
Correct |
13 ms |
23820 KB |
n=100 |
14 |
Correct |
12 ms |
23816 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23764 KB |
n=100 |
18 |
Correct |
12 ms |
23764 KB |
n=100 |
19 |
Correct |
12 ms |
23816 KB |
n=100 |
20 |
Correct |
12 ms |
23764 KB |
n=100 |
21 |
Correct |
12 ms |
23844 KB |
n=100 |
22 |
Correct |
12 ms |
23804 KB |
n=100 |
23 |
Correct |
12 ms |
23840 KB |
n=100 |
24 |
Correct |
14 ms |
23796 KB |
n=100 |
25 |
Correct |
12 ms |
23764 KB |
n=100 |
26 |
Correct |
13 ms |
23764 KB |
n=12 |
27 |
Correct |
13 ms |
23784 KB |
n=100 |
28 |
Correct |
13 ms |
23964 KB |
n=500 |
29 |
Correct |
13 ms |
23960 KB |
n=500 |
30 |
Correct |
13 ms |
23892 KB |
n=500 |
31 |
Correct |
12 ms |
23972 KB |
n=500 |
32 |
Correct |
13 ms |
23960 KB |
n=500 |
33 |
Correct |
13 ms |
23960 KB |
n=500 |
34 |
Correct |
13 ms |
23992 KB |
n=500 |
35 |
Correct |
13 ms |
23892 KB |
n=500 |
36 |
Correct |
12 ms |
23892 KB |
n=500 |
37 |
Correct |
13 ms |
23892 KB |
n=500 |
38 |
Correct |
12 ms |
23892 KB |
n=500 |
39 |
Correct |
16 ms |
23892 KB |
n=500 |
40 |
Correct |
15 ms |
23908 KB |
n=500 |
41 |
Correct |
13 ms |
23960 KB |
n=500 |
42 |
Correct |
14 ms |
23956 KB |
n=500 |
43 |
Correct |
15 ms |
23892 KB |
n=500 |
44 |
Correct |
13 ms |
23964 KB |
n=500 |
45 |
Correct |
13 ms |
23892 KB |
n=500 |
46 |
Correct |
12 ms |
24016 KB |
n=500 |
47 |
Correct |
15 ms |
23960 KB |
n=500 |
48 |
Correct |
12 ms |
23892 KB |
n=500 |
49 |
Correct |
13 ms |
23892 KB |
n=500 |
50 |
Correct |
15 ms |
23980 KB |
n=500 |
51 |
Correct |
12 ms |
23960 KB |
n=500 |
52 |
Correct |
13 ms |
23944 KB |
n=500 |
53 |
Correct |
12 ms |
23892 KB |
n=500 |
54 |
Correct |
14 ms |
23892 KB |
n=500 |
55 |
Correct |
12 ms |
23892 KB |
n=278 |
56 |
Correct |
13 ms |
23956 KB |
n=500 |
57 |
Correct |
12 ms |
23924 KB |
n=500 |
58 |
Correct |
13 ms |
23892 KB |
n=500 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
n=5 |
2 |
Correct |
12 ms |
23764 KB |
n=100 |
3 |
Correct |
13 ms |
23804 KB |
n=100 |
4 |
Correct |
12 ms |
23816 KB |
n=100 |
5 |
Correct |
12 ms |
23812 KB |
n=100 |
6 |
Correct |
11 ms |
23820 KB |
n=100 |
7 |
Correct |
13 ms |
23764 KB |
n=100 |
8 |
Correct |
12 ms |
23856 KB |
n=100 |
9 |
Correct |
14 ms |
23808 KB |
n=100 |
10 |
Correct |
13 ms |
23812 KB |
n=100 |
11 |
Correct |
12 ms |
23764 KB |
n=100 |
12 |
Correct |
15 ms |
23764 KB |
n=100 |
13 |
Correct |
13 ms |
23820 KB |
n=100 |
14 |
Correct |
12 ms |
23816 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23764 KB |
n=100 |
18 |
Correct |
12 ms |
23764 KB |
n=100 |
19 |
Correct |
12 ms |
23816 KB |
n=100 |
20 |
Correct |
12 ms |
23764 KB |
n=100 |
21 |
Correct |
12 ms |
23844 KB |
n=100 |
22 |
Correct |
12 ms |
23804 KB |
n=100 |
23 |
Correct |
12 ms |
23840 KB |
n=100 |
24 |
Correct |
14 ms |
23796 KB |
n=100 |
25 |
Correct |
12 ms |
23764 KB |
n=100 |
26 |
Correct |
13 ms |
23764 KB |
n=12 |
27 |
Correct |
13 ms |
23784 KB |
n=100 |
28 |
Correct |
13 ms |
23964 KB |
n=500 |
29 |
Correct |
13 ms |
23960 KB |
n=500 |
30 |
Correct |
13 ms |
23892 KB |
n=500 |
31 |
Correct |
12 ms |
23972 KB |
n=500 |
32 |
Correct |
13 ms |
23960 KB |
n=500 |
33 |
Correct |
13 ms |
23960 KB |
n=500 |
34 |
Correct |
13 ms |
23992 KB |
n=500 |
35 |
Correct |
13 ms |
23892 KB |
n=500 |
36 |
Correct |
12 ms |
23892 KB |
n=500 |
37 |
Correct |
13 ms |
23892 KB |
n=500 |
38 |
Correct |
12 ms |
23892 KB |
n=500 |
39 |
Correct |
16 ms |
23892 KB |
n=500 |
40 |
Correct |
15 ms |
23908 KB |
n=500 |
41 |
Correct |
13 ms |
23960 KB |
n=500 |
42 |
Correct |
14 ms |
23956 KB |
n=500 |
43 |
Correct |
15 ms |
23892 KB |
n=500 |
44 |
Correct |
13 ms |
23964 KB |
n=500 |
45 |
Correct |
13 ms |
23892 KB |
n=500 |
46 |
Correct |
12 ms |
24016 KB |
n=500 |
47 |
Correct |
15 ms |
23960 KB |
n=500 |
48 |
Correct |
12 ms |
23892 KB |
n=500 |
49 |
Correct |
13 ms |
23892 KB |
n=500 |
50 |
Correct |
15 ms |
23980 KB |
n=500 |
51 |
Correct |
12 ms |
23960 KB |
n=500 |
52 |
Correct |
13 ms |
23944 KB |
n=500 |
53 |
Correct |
12 ms |
23892 KB |
n=500 |
54 |
Correct |
14 ms |
23892 KB |
n=500 |
55 |
Correct |
12 ms |
23892 KB |
n=278 |
56 |
Correct |
13 ms |
23956 KB |
n=500 |
57 |
Correct |
12 ms |
23924 KB |
n=500 |
58 |
Correct |
13 ms |
23892 KB |
n=500 |
59 |
Correct |
18 ms |
24468 KB |
n=2000 |
60 |
Correct |
14 ms |
24556 KB |
n=2000 |
61 |
Correct |
14 ms |
24432 KB |
n=2000 |
62 |
Correct |
15 ms |
24412 KB |
n=2000 |
63 |
Correct |
15 ms |
24404 KB |
n=2000 |
64 |
Correct |
15 ms |
24404 KB |
n=2000 |
65 |
Correct |
15 ms |
24476 KB |
n=2000 |
66 |
Correct |
15 ms |
24532 KB |
n=2000 |
67 |
Correct |
17 ms |
24404 KB |
n=2000 |
68 |
Correct |
15 ms |
24448 KB |
n=2000 |
69 |
Correct |
14 ms |
24424 KB |
n=2000 |
70 |
Correct |
14 ms |
24448 KB |
n=2000 |
71 |
Correct |
16 ms |
24436 KB |
n=2000 |
72 |
Correct |
14 ms |
24404 KB |
n=2000 |
73 |
Correct |
14 ms |
24404 KB |
n=2000 |
74 |
Correct |
15 ms |
24328 KB |
n=1844 |
75 |
Correct |
17 ms |
24460 KB |
n=2000 |
76 |
Correct |
17 ms |
24480 KB |
n=2000 |
77 |
Correct |
18 ms |
24400 KB |
n=2000 |
78 |
Correct |
15 ms |
24388 KB |
n=2000 |
79 |
Correct |
16 ms |
24468 KB |
n=2000 |
80 |
Correct |
16 ms |
24548 KB |
n=2000 |
81 |
Correct |
18 ms |
24516 KB |
n=2000 |
82 |
Correct |
16 ms |
24468 KB |
n=2000 |
83 |
Correct |
15 ms |
24468 KB |
n=2000 |
84 |
Correct |
19 ms |
24404 KB |
n=2000 |
85 |
Correct |
15 ms |
24404 KB |
n=2000 |
86 |
Correct |
15 ms |
24496 KB |
n=2000 |
87 |
Correct |
16 ms |
24404 KB |
n=2000 |
88 |
Correct |
15 ms |
24472 KB |
n=2000 |
89 |
Correct |
15 ms |
24532 KB |
n=2000 |
90 |
Correct |
15 ms |
24532 KB |
n=2000 |
91 |
Correct |
16 ms |
24404 KB |
n=2000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
n=5 |
2 |
Correct |
12 ms |
23764 KB |
n=100 |
3 |
Correct |
13 ms |
23804 KB |
n=100 |
4 |
Correct |
12 ms |
23816 KB |
n=100 |
5 |
Correct |
12 ms |
23812 KB |
n=100 |
6 |
Correct |
11 ms |
23820 KB |
n=100 |
7 |
Correct |
13 ms |
23764 KB |
n=100 |
8 |
Correct |
12 ms |
23856 KB |
n=100 |
9 |
Correct |
14 ms |
23808 KB |
n=100 |
10 |
Correct |
13 ms |
23812 KB |
n=100 |
11 |
Correct |
12 ms |
23764 KB |
n=100 |
12 |
Correct |
15 ms |
23764 KB |
n=100 |
13 |
Correct |
13 ms |
23820 KB |
n=100 |
14 |
Correct |
12 ms |
23816 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23764 KB |
n=100 |
18 |
Correct |
12 ms |
23764 KB |
n=100 |
19 |
Correct |
12 ms |
23816 KB |
n=100 |
20 |
Correct |
12 ms |
23764 KB |
n=100 |
21 |
Correct |
12 ms |
23844 KB |
n=100 |
22 |
Correct |
12 ms |
23804 KB |
n=100 |
23 |
Correct |
12 ms |
23840 KB |
n=100 |
24 |
Correct |
14 ms |
23796 KB |
n=100 |
25 |
Correct |
12 ms |
23764 KB |
n=100 |
26 |
Correct |
13 ms |
23764 KB |
n=12 |
27 |
Correct |
13 ms |
23784 KB |
n=100 |
28 |
Correct |
13 ms |
23964 KB |
n=500 |
29 |
Correct |
13 ms |
23960 KB |
n=500 |
30 |
Correct |
13 ms |
23892 KB |
n=500 |
31 |
Correct |
12 ms |
23972 KB |
n=500 |
32 |
Correct |
13 ms |
23960 KB |
n=500 |
33 |
Correct |
13 ms |
23960 KB |
n=500 |
34 |
Correct |
13 ms |
23992 KB |
n=500 |
35 |
Correct |
13 ms |
23892 KB |
n=500 |
36 |
Correct |
12 ms |
23892 KB |
n=500 |
37 |
Correct |
13 ms |
23892 KB |
n=500 |
38 |
Correct |
12 ms |
23892 KB |
n=500 |
39 |
Correct |
16 ms |
23892 KB |
n=500 |
40 |
Correct |
15 ms |
23908 KB |
n=500 |
41 |
Correct |
13 ms |
23960 KB |
n=500 |
42 |
Correct |
14 ms |
23956 KB |
n=500 |
43 |
Correct |
15 ms |
23892 KB |
n=500 |
44 |
Correct |
13 ms |
23964 KB |
n=500 |
45 |
Correct |
13 ms |
23892 KB |
n=500 |
46 |
Correct |
12 ms |
24016 KB |
n=500 |
47 |
Correct |
15 ms |
23960 KB |
n=500 |
48 |
Correct |
12 ms |
23892 KB |
n=500 |
49 |
Correct |
13 ms |
23892 KB |
n=500 |
50 |
Correct |
15 ms |
23980 KB |
n=500 |
51 |
Correct |
12 ms |
23960 KB |
n=500 |
52 |
Correct |
13 ms |
23944 KB |
n=500 |
53 |
Correct |
12 ms |
23892 KB |
n=500 |
54 |
Correct |
14 ms |
23892 KB |
n=500 |
55 |
Correct |
12 ms |
23892 KB |
n=278 |
56 |
Correct |
13 ms |
23956 KB |
n=500 |
57 |
Correct |
12 ms |
23924 KB |
n=500 |
58 |
Correct |
13 ms |
23892 KB |
n=500 |
59 |
Correct |
18 ms |
24468 KB |
n=2000 |
60 |
Correct |
14 ms |
24556 KB |
n=2000 |
61 |
Correct |
14 ms |
24432 KB |
n=2000 |
62 |
Correct |
15 ms |
24412 KB |
n=2000 |
63 |
Correct |
15 ms |
24404 KB |
n=2000 |
64 |
Correct |
15 ms |
24404 KB |
n=2000 |
65 |
Correct |
15 ms |
24476 KB |
n=2000 |
66 |
Correct |
15 ms |
24532 KB |
n=2000 |
67 |
Correct |
17 ms |
24404 KB |
n=2000 |
68 |
Correct |
15 ms |
24448 KB |
n=2000 |
69 |
Correct |
14 ms |
24424 KB |
n=2000 |
70 |
Correct |
14 ms |
24448 KB |
n=2000 |
71 |
Correct |
16 ms |
24436 KB |
n=2000 |
72 |
Correct |
14 ms |
24404 KB |
n=2000 |
73 |
Correct |
14 ms |
24404 KB |
n=2000 |
74 |
Correct |
15 ms |
24328 KB |
n=1844 |
75 |
Correct |
17 ms |
24460 KB |
n=2000 |
76 |
Correct |
17 ms |
24480 KB |
n=2000 |
77 |
Correct |
18 ms |
24400 KB |
n=2000 |
78 |
Correct |
15 ms |
24388 KB |
n=2000 |
79 |
Correct |
16 ms |
24468 KB |
n=2000 |
80 |
Correct |
16 ms |
24548 KB |
n=2000 |
81 |
Correct |
18 ms |
24516 KB |
n=2000 |
82 |
Correct |
16 ms |
24468 KB |
n=2000 |
83 |
Correct |
15 ms |
24468 KB |
n=2000 |
84 |
Correct |
19 ms |
24404 KB |
n=2000 |
85 |
Correct |
15 ms |
24404 KB |
n=2000 |
86 |
Correct |
15 ms |
24496 KB |
n=2000 |
87 |
Correct |
16 ms |
24404 KB |
n=2000 |
88 |
Correct |
15 ms |
24472 KB |
n=2000 |
89 |
Correct |
15 ms |
24532 KB |
n=2000 |
90 |
Correct |
15 ms |
24532 KB |
n=2000 |
91 |
Correct |
16 ms |
24404 KB |
n=2000 |
92 |
Correct |
742 ms |
90968 KB |
n=200000 |
93 |
Correct |
1047 ms |
95876 KB |
n=200000 |
94 |
Correct |
994 ms |
98752 KB |
n=200000 |
95 |
Correct |
685 ms |
90740 KB |
n=200000 |
96 |
Correct |
694 ms |
90844 KB |
n=200000 |
97 |
Correct |
1068 ms |
95104 KB |
n=200000 |
98 |
Correct |
722 ms |
90472 KB |
n=200000 |
99 |
Correct |
957 ms |
91140 KB |
n=200000 |
100 |
Correct |
700 ms |
90820 KB |
n=200000 |
101 |
Correct |
988 ms |
99864 KB |
n=200000 |
102 |
Correct |
436 ms |
92156 KB |
n=200000 |
103 |
Correct |
424 ms |
92180 KB |
n=200000 |
104 |
Correct |
476 ms |
92120 KB |
n=200000 |
105 |
Correct |
441 ms |
92652 KB |
n=200000 |
106 |
Correct |
445 ms |
92644 KB |
n=200000 |
107 |
Correct |
487 ms |
92624 KB |
n=200000 |
108 |
Correct |
890 ms |
91040 KB |
n=200000 |
109 |
Correct |
837 ms |
91096 KB |
n=200000 |
110 |
Correct |
882 ms |
91056 KB |
n=200000 |
111 |
Correct |
707 ms |
90356 KB |
n=200000 |
112 |
Correct |
980 ms |
99080 KB |
n=200000 |
113 |
Correct |
1090 ms |
95048 KB |
n=200000 |
114 |
Correct |
708 ms |
90432 KB |
n=200000 |
115 |
Correct |
1202 ms |
93104 KB |
n=200000 |
116 |
Correct |
666 ms |
90984 KB |
n=200000 |
117 |
Correct |
988 ms |
99404 KB |
n=200000 |
118 |
Correct |
1089 ms |
93920 KB |
n=200000 |
119 |
Correct |
709 ms |
90840 KB |
n=200000 |
120 |
Correct |
953 ms |
98676 KB |
n=200000 |
121 |
Correct |
964 ms |
98652 KB |
n=200000 |
122 |
Correct |
951 ms |
98988 KB |
n=200000 |
123 |
Correct |
478 ms |
92380 KB |
n=200000 |
124 |
Incorrect |
203 ms |
41072 KB |
Wrong range. |
125 |
Halted |
0 ms |
0 KB |
- |