#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <pair <int,int> > g[N];
int a[N],b[N],c[N],d[N];
void dfs(int v,int p){
for(auto to : g[v]){
if(to.ff!=p){
d[to.ff]=d[v]+c[to.ss];
dfs(to.ff,v);
}
}
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,q,w;
cin>>n>>q>>w;
int cnt=0;
multiset <int> ms;
for(int i=0;i<n-1;i++){
cin>>a[i]>>b[i]>>c[i];
g[a[i]].pb({b[i],i});
g[b[i]].pb({a[i],i});
if(1==a[i] or b[i]==1)cnt++;
ms.insert(c[i]);
}
bool sbtsk3=0;
if(cnt==n-1)sbtsk3=1;
int last=0;
for(int i=0;i<q;i++){
int ind,val;
cin>>ind>>val;
ind=(ind+last)%(n-1);
val=(val+last)%w;
ms.erase(ms.find(c[ind]));
ms.insert(val);
c[ind]=val;
if(sbtsk3){
int ans=*ms.rbegin();
if(ms.size()>=2){
ms.erase(ms.find(ans));
int x=*ms.rbegin();
ms.insert(ans);
ans+=x;
}
cout<<ans<<"\n";
last=ans;
}
else{
for(int i=1;i<=n;i++)d[i]=0;
dfs(1,0);
int root=1,mx=0;
for(int i=1;i<=n;i++){
if(mx<d[i]){
mx=d[i];root=i;
}
}
for(int i=1;i<=n;i++)d[i]=0;
dfs(root,0);
mx=0;
for(int i=1;i<=n;i++)mx=max(mx,d[i]);
last=mx;
cout<<mx<<"\n";
}
}
}
/*
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5720 KB |
Output is correct |
2 |
Correct |
1 ms |
5724 KB |
Output is correct |
3 |
Correct |
1 ms |
5724 KB |
Output is correct |
4 |
Correct |
2 ms |
5720 KB |
Output is correct |
5 |
Correct |
1 ms |
5724 KB |
Output is correct |
6 |
Correct |
1 ms |
5724 KB |
Output is correct |
7 |
Correct |
2 ms |
5724 KB |
Output is correct |
8 |
Correct |
2 ms |
5724 KB |
Output is correct |
9 |
Correct |
1 ms |
5724 KB |
Output is correct |
10 |
Correct |
1 ms |
5724 KB |
Output is correct |
11 |
Correct |
2 ms |
5724 KB |
Output is correct |
12 |
Correct |
2 ms |
5724 KB |
Output is correct |
13 |
Correct |
2 ms |
5980 KB |
Output is correct |
14 |
Correct |
2 ms |
5740 KB |
Output is correct |
15 |
Correct |
2 ms |
5724 KB |
Output is correct |
16 |
Correct |
2 ms |
5724 KB |
Output is correct |
17 |
Correct |
2 ms |
5724 KB |
Output is correct |
18 |
Correct |
2 ms |
5724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5720 KB |
Output is correct |
2 |
Correct |
1 ms |
5724 KB |
Output is correct |
3 |
Correct |
1 ms |
5724 KB |
Output is correct |
4 |
Correct |
2 ms |
5720 KB |
Output is correct |
5 |
Correct |
1 ms |
5724 KB |
Output is correct |
6 |
Correct |
1 ms |
5724 KB |
Output is correct |
7 |
Correct |
2 ms |
5724 KB |
Output is correct |
8 |
Correct |
2 ms |
5724 KB |
Output is correct |
9 |
Correct |
1 ms |
5724 KB |
Output is correct |
10 |
Correct |
1 ms |
5724 KB |
Output is correct |
11 |
Correct |
2 ms |
5724 KB |
Output is correct |
12 |
Correct |
2 ms |
5724 KB |
Output is correct |
13 |
Correct |
2 ms |
5980 KB |
Output is correct |
14 |
Correct |
2 ms |
5740 KB |
Output is correct |
15 |
Correct |
2 ms |
5724 KB |
Output is correct |
16 |
Correct |
2 ms |
5724 KB |
Output is correct |
17 |
Correct |
2 ms |
5724 KB |
Output is correct |
18 |
Correct |
2 ms |
5724 KB |
Output is correct |
19 |
Correct |
72 ms |
5724 KB |
Output is correct |
20 |
Correct |
80 ms |
5908 KB |
Output is correct |
21 |
Correct |
88 ms |
5908 KB |
Output is correct |
22 |
Correct |
123 ms |
5980 KB |
Output is correct |
23 |
Correct |
929 ms |
6404 KB |
Output is correct |
24 |
Correct |
1098 ms |
6416 KB |
Output is correct |
25 |
Correct |
1190 ms |
6464 KB |
Output is correct |
26 |
Correct |
1385 ms |
6996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5724 KB |
Output is correct |
2 |
Correct |
2 ms |
5724 KB |
Output is correct |
3 |
Correct |
3 ms |
5724 KB |
Output is correct |
4 |
Correct |
11 ms |
5724 KB |
Output is correct |
5 |
Correct |
53 ms |
6720 KB |
Output is correct |
6 |
Correct |
2 ms |
5724 KB |
Output is correct |
7 |
Correct |
2 ms |
5724 KB |
Output is correct |
8 |
Correct |
2 ms |
5724 KB |
Output is correct |
9 |
Correct |
3 ms |
5724 KB |
Output is correct |
10 |
Correct |
13 ms |
6012 KB |
Output is correct |
11 |
Correct |
60 ms |
6992 KB |
Output is correct |
12 |
Correct |
5 ms |
6232 KB |
Output is correct |
13 |
Correct |
5 ms |
6236 KB |
Output is correct |
14 |
Correct |
6 ms |
6232 KB |
Output is correct |
15 |
Correct |
17 ms |
6460 KB |
Output is correct |
16 |
Correct |
69 ms |
7352 KB |
Output is correct |
17 |
Correct |
77 ms |
16324 KB |
Output is correct |
18 |
Correct |
78 ms |
16280 KB |
Output is correct |
19 |
Correct |
85 ms |
16320 KB |
Output is correct |
20 |
Correct |
93 ms |
16208 KB |
Output is correct |
21 |
Correct |
187 ms |
17112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
5724 KB |
Output is correct |
2 |
Correct |
123 ms |
5972 KB |
Output is correct |
3 |
Correct |
626 ms |
6652 KB |
Output is correct |
4 |
Correct |
1223 ms |
7148 KB |
Output is correct |
5 |
Correct |
129 ms |
6964 KB |
Output is correct |
6 |
Correct |
1275 ms |
7312 KB |
Output is correct |
7 |
Execution timed out |
5011 ms |
7988 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5031 ms |
17356 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5720 KB |
Output is correct |
2 |
Correct |
1 ms |
5724 KB |
Output is correct |
3 |
Correct |
1 ms |
5724 KB |
Output is correct |
4 |
Correct |
2 ms |
5720 KB |
Output is correct |
5 |
Correct |
1 ms |
5724 KB |
Output is correct |
6 |
Correct |
1 ms |
5724 KB |
Output is correct |
7 |
Correct |
2 ms |
5724 KB |
Output is correct |
8 |
Correct |
2 ms |
5724 KB |
Output is correct |
9 |
Correct |
1 ms |
5724 KB |
Output is correct |
10 |
Correct |
1 ms |
5724 KB |
Output is correct |
11 |
Correct |
2 ms |
5724 KB |
Output is correct |
12 |
Correct |
2 ms |
5724 KB |
Output is correct |
13 |
Correct |
2 ms |
5980 KB |
Output is correct |
14 |
Correct |
2 ms |
5740 KB |
Output is correct |
15 |
Correct |
2 ms |
5724 KB |
Output is correct |
16 |
Correct |
2 ms |
5724 KB |
Output is correct |
17 |
Correct |
2 ms |
5724 KB |
Output is correct |
18 |
Correct |
2 ms |
5724 KB |
Output is correct |
19 |
Correct |
72 ms |
5724 KB |
Output is correct |
20 |
Correct |
80 ms |
5908 KB |
Output is correct |
21 |
Correct |
88 ms |
5908 KB |
Output is correct |
22 |
Correct |
123 ms |
5980 KB |
Output is correct |
23 |
Correct |
929 ms |
6404 KB |
Output is correct |
24 |
Correct |
1098 ms |
6416 KB |
Output is correct |
25 |
Correct |
1190 ms |
6464 KB |
Output is correct |
26 |
Correct |
1385 ms |
6996 KB |
Output is correct |
27 |
Correct |
2 ms |
5724 KB |
Output is correct |
28 |
Correct |
2 ms |
5724 KB |
Output is correct |
29 |
Correct |
3 ms |
5724 KB |
Output is correct |
30 |
Correct |
11 ms |
5724 KB |
Output is correct |
31 |
Correct |
53 ms |
6720 KB |
Output is correct |
32 |
Correct |
2 ms |
5724 KB |
Output is correct |
33 |
Correct |
2 ms |
5724 KB |
Output is correct |
34 |
Correct |
2 ms |
5724 KB |
Output is correct |
35 |
Correct |
3 ms |
5724 KB |
Output is correct |
36 |
Correct |
13 ms |
6012 KB |
Output is correct |
37 |
Correct |
60 ms |
6992 KB |
Output is correct |
38 |
Correct |
5 ms |
6232 KB |
Output is correct |
39 |
Correct |
5 ms |
6236 KB |
Output is correct |
40 |
Correct |
6 ms |
6232 KB |
Output is correct |
41 |
Correct |
17 ms |
6460 KB |
Output is correct |
42 |
Correct |
69 ms |
7352 KB |
Output is correct |
43 |
Correct |
77 ms |
16324 KB |
Output is correct |
44 |
Correct |
78 ms |
16280 KB |
Output is correct |
45 |
Correct |
85 ms |
16320 KB |
Output is correct |
46 |
Correct |
93 ms |
16208 KB |
Output is correct |
47 |
Correct |
187 ms |
17112 KB |
Output is correct |
48 |
Correct |
14 ms |
5724 KB |
Output is correct |
49 |
Correct |
123 ms |
5972 KB |
Output is correct |
50 |
Correct |
626 ms |
6652 KB |
Output is correct |
51 |
Correct |
1223 ms |
7148 KB |
Output is correct |
52 |
Correct |
129 ms |
6964 KB |
Output is correct |
53 |
Correct |
1275 ms |
7312 KB |
Output is correct |
54 |
Execution timed out |
5011 ms |
7988 KB |
Time limit exceeded |
55 |
Halted |
0 ms |
0 KB |
- |