/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
struct segtree
{
vector<LL> d;
vector<pair<LL,int>> t;
void build(int v,int l,int r,vector<int> &a,vector<LL>& D,unordered_map<int,int>&b)
{
if(l==r)
{
t[v].first=D[a[l]];
t[v].second=b[a[l]];
d[v]=0;
return;
}
int m=(l+r)/2;
build(v*2,l,m,a,D,b);
build(v*2+1,m+1,r,a,D,b);
t[v]=max(t[v*2],t[v*2+1]);
}
segtree(int n=0)
{
t.resize(n*4+5);
d.resize(n*4+5);
}
segtree(vector<int>& a,vector<LL>& D,unordered_map<int,int>& b)
{
t.resize(a.size()*4+5);
d.resize(a.size()*4+5);
build(1,0,a.size()-1,a,D,b);
}
void push(int v,int l,int r,int f=1)
{
if(d[v]==0)
return;
if(l!=r)
{
int m=(l+r)/2;
d[v*2]+=d[v];
d[v*2+1]+=d[v];
if(f)
{
push(v*2,l,m,0);
push(v*2+1,m+1,r,0);
}
}
t[v].first+=d[v];
d[v]=0;
}
pair<LL,int> get(int v,int l,int r,int i,int j)
{
push(v,l,r);
if(i>j)
return MP(0,0);
if(l==i && r==j)
return t[v];
int m=(l+r)/2;
return max(
get(v*2,l,m,i,min(j,m)),
get(v*2+1,m+1,r,max(i,m+1),j)
);
}
void add(int v,int l,int r,int i,int j,LL val)
{
push(v,l,r);
if(i>j)
return;
if(l==i && r==j)
{
d[v]+=val;
push(v,l,r);
return;
}
int m=(l+r)/2;
add(v*2,l,m,i,min(j,m),val);
add(v*2+1,m+1,r,max(i,m+1),j,val);
t[v]=max(t[v*2],t[v*2+1]);
}
};
LL n, q;
LL W, w[100005],sz[100005],used[100005],color[100005],col, ans;
vector<LL> d(100005);
vector<pair<int, int>> g[100005];
vector<int> ord[100005];
segtree seg[100005];
unordered_map<int,int> subtree[100005],tin[100005],tout[100005],pos[100005],centr[100005];
multiset<LL> best;
void dfsSize(int v,int p)
{
color[v]=col;
sz[v]=1;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
if(used[to] || to==p)
continue;
dfsSize(to,v);
sz[v]+=sz[to];
}
}
int centroid(int v)
{
col++;
dfsSize(v,0);
col++;
queue<int> q;
q.push(v);
while (!q.empty())
{
int x=q.front();
q.pop();
color[x]=col;
bool is=(sz[v]>=(sz[v]-sz[x])*2);
for(int i=0;i<g[x].size();i++)
{
int to=g[x][i].first;
if(color[to]==col || used[to])
continue;
q.push(to);
is&=(sz[v]>=sz[to]*2);
}
if(is)
return x;
}
}
void dfs(int Centr,int Sub,int v,int p,LL dist)
{
d[v]=dist;
subtree[Centr][v]=Sub;
ord[Centr].PB(v);
tin[Centr][v]=ord[Centr].size()-1;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
int d=g[v][i].second;
if(to==p || used[to])
continue;
pos[Centr][d]=to;
dfs(Centr,Sub,to,v,dist+w[d]);
}
tout[Centr][v]=ord[Centr].size()-1;
}
LL getMax(int v)
{
pair<LL, LL> mx1,mx2;
mx1 = seg[v].get(1, 0, ord[v].size() - 1, 0, ord[v].size() - 1);
if(mx1.first==0)
return 0;
mx2 = max(
seg[v].get(1, 0, ord[v].size() - 1, 0, tin[v][mx1.second] - 1),
seg[v].get(1, 0, ord[v].size() - 1, tout[v][mx1.second] + 1, ord[v].size() - 1)
);
return mx1.first+mx2.first;
}
void calc(int v)
{
used[v]=1;
ord[v].PB(v);
tin[v][v]=ord[v].size()-1;
d[v]=0;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
int d=g[v][i].second;
if(used[to])
continue;
pos[v][d]=to;
dfs(v,to,to,v,w[d]);
}
tout[v][v]=ord[v].size()-1;
seg[v]=segtree(ord[v],d,subtree[v]);
LL mx=getMax(v);
//cout<<"!!!"<<v<<" > "<<mx<<endl;
best.insert(mx);
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
if(used[to])
continue;
calc(centr[v][to]=centroid(to));
}
}
void solve(int v,int P,LL val)
{
if(pos[v].find(P)==pos[v].end())
return;
int p=pos[v][P];
LL mx;
mx=getMax(v);
//cout<<"!!"<<v<<" > "<<mx<<endl;
best.erase(best.find(mx));
seg[v].add(1, 0, ord[v].size() - 1, tin[v][p], tout[v][p], val);
mx=getMax(v);
//cout<<"!"<<v<<" > "<<mx<<endl;
best.insert(mx);
solve(centr[v][subtree[v][p]],P,val);
}
int main()
{
cin >> n >> q >> W;
for (int i = 1; i <= n - 1; i++)
{
int a, b;
scanf("%d%d%lld", &a, &b, w + i);
g[a].PB(MP(b, i));
g[b].PB(MP(a, i));
}
calc(centr[0][1]=centroid(1));
while (q--)
{
LL p;
LL D;
scanf("%lld%lld", &p, &D);
p = (p + ans) % (n - 1);
D = (D + ans) % W;
p++;
solve(centr[0][1],p,D-w[p]);
w[p]=D;
if(!best.empty())
{
auto it=best.end();
--it;
ans=(*it);
}
else
ans=0;
printf("%lld\n", ans);
}
return 0;
}
/*
7 1 1000
1 2 10
2 3 1
2 4 1
1 5 1
5 6 1
5 7 1
0 1
*/
Compilation message
diameter.cpp: In function 'void dfsSize(int, int)':
diameter.cpp:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:146:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++)
~^~~~~~~~~~~~
diameter.cpp: In function 'void dfs(int, int, int, int, long long int)':
diameter.cpp:167:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
diameter.cpp: In function 'void calc(int)':
diameter.cpp:201:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
diameter.cpp:218:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:158:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
diameter.cpp: In function 'int main()':
diameter.cpp:253:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &a, &b, w + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:262:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &p, &D);
~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
52104 KB |
Output is correct |
2 |
Correct |
47 ms |
52088 KB |
Output is correct |
3 |
Correct |
43 ms |
52088 KB |
Output is correct |
4 |
Correct |
44 ms |
51960 KB |
Output is correct |
5 |
Correct |
43 ms |
51960 KB |
Output is correct |
6 |
Correct |
44 ms |
51960 KB |
Output is correct |
7 |
Correct |
45 ms |
52088 KB |
Output is correct |
8 |
Correct |
43 ms |
52088 KB |
Output is correct |
9 |
Correct |
43 ms |
52088 KB |
Output is correct |
10 |
Correct |
45 ms |
52088 KB |
Output is correct |
11 |
Correct |
43 ms |
52088 KB |
Output is correct |
12 |
Correct |
45 ms |
52088 KB |
Output is correct |
13 |
Correct |
46 ms |
52088 KB |
Output is correct |
14 |
Correct |
45 ms |
52216 KB |
Output is correct |
15 |
Correct |
45 ms |
52088 KB |
Output is correct |
16 |
Correct |
44 ms |
52088 KB |
Output is correct |
17 |
Correct |
44 ms |
52216 KB |
Output is correct |
18 |
Correct |
44 ms |
52216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
52104 KB |
Output is correct |
2 |
Correct |
47 ms |
52088 KB |
Output is correct |
3 |
Correct |
43 ms |
52088 KB |
Output is correct |
4 |
Correct |
44 ms |
51960 KB |
Output is correct |
5 |
Correct |
43 ms |
51960 KB |
Output is correct |
6 |
Correct |
44 ms |
51960 KB |
Output is correct |
7 |
Correct |
45 ms |
52088 KB |
Output is correct |
8 |
Correct |
43 ms |
52088 KB |
Output is correct |
9 |
Correct |
43 ms |
52088 KB |
Output is correct |
10 |
Correct |
45 ms |
52088 KB |
Output is correct |
11 |
Correct |
43 ms |
52088 KB |
Output is correct |
12 |
Correct |
45 ms |
52088 KB |
Output is correct |
13 |
Correct |
46 ms |
52088 KB |
Output is correct |
14 |
Correct |
45 ms |
52216 KB |
Output is correct |
15 |
Correct |
45 ms |
52088 KB |
Output is correct |
16 |
Correct |
44 ms |
52088 KB |
Output is correct |
17 |
Correct |
44 ms |
52216 KB |
Output is correct |
18 |
Correct |
44 ms |
52216 KB |
Output is correct |
19 |
Correct |
87 ms |
53880 KB |
Output is correct |
20 |
Correct |
86 ms |
54008 KB |
Output is correct |
21 |
Correct |
97 ms |
54396 KB |
Output is correct |
22 |
Correct |
103 ms |
54776 KB |
Output is correct |
23 |
Correct |
164 ms |
62712 KB |
Output is correct |
24 |
Correct |
204 ms |
65272 KB |
Output is correct |
25 |
Correct |
207 ms |
66424 KB |
Output is correct |
26 |
Correct |
223 ms |
69016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
51964 KB |
Output is correct |
2 |
Correct |
44 ms |
52136 KB |
Output is correct |
3 |
Correct |
45 ms |
52088 KB |
Output is correct |
4 |
Correct |
61 ms |
52216 KB |
Output is correct |
5 |
Correct |
133 ms |
53112 KB |
Output is correct |
6 |
Correct |
44 ms |
51964 KB |
Output is correct |
7 |
Correct |
44 ms |
52344 KB |
Output is correct |
8 |
Correct |
45 ms |
52344 KB |
Output is correct |
9 |
Correct |
47 ms |
52472 KB |
Output is correct |
10 |
Correct |
73 ms |
52728 KB |
Output is correct |
11 |
Correct |
175 ms |
53756 KB |
Output is correct |
12 |
Correct |
60 ms |
55800 KB |
Output is correct |
13 |
Correct |
62 ms |
55804 KB |
Output is correct |
14 |
Correct |
65 ms |
55800 KB |
Output is correct |
15 |
Correct |
105 ms |
56056 KB |
Output is correct |
16 |
Correct |
242 ms |
57208 KB |
Output is correct |
17 |
Correct |
347 ms |
126060 KB |
Output is correct |
18 |
Correct |
345 ms |
125932 KB |
Output is correct |
19 |
Correct |
356 ms |
126060 KB |
Output is correct |
20 |
Correct |
396 ms |
126036 KB |
Output is correct |
21 |
Correct |
688 ms |
126828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
54392 KB |
Output is correct |
2 |
Correct |
107 ms |
54520 KB |
Output is correct |
3 |
Correct |
304 ms |
55072 KB |
Output is correct |
4 |
Correct |
534 ms |
55800 KB |
Output is correct |
5 |
Correct |
181 ms |
84856 KB |
Output is correct |
6 |
Correct |
296 ms |
84984 KB |
Output is correct |
7 |
Correct |
760 ms |
86008 KB |
Output is correct |
8 |
Correct |
1406 ms |
86404 KB |
Output is correct |
9 |
Correct |
857 ms |
248072 KB |
Output is correct |
10 |
Correct |
1012 ms |
248324 KB |
Output is correct |
11 |
Correct |
1883 ms |
248652 KB |
Output is correct |
12 |
Correct |
2910 ms |
249140 KB |
Output is correct |
13 |
Correct |
1914 ms |
470648 KB |
Output is correct |
14 |
Correct |
2024 ms |
470532 KB |
Output is correct |
15 |
Correct |
3018 ms |
471044 KB |
Output is correct |
16 |
Correct |
4351 ms |
471424 KB |
Output is correct |
17 |
Execution timed out |
5104 ms |
471008 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5051 ms |
367864 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
52104 KB |
Output is correct |
2 |
Correct |
47 ms |
52088 KB |
Output is correct |
3 |
Correct |
43 ms |
52088 KB |
Output is correct |
4 |
Correct |
44 ms |
51960 KB |
Output is correct |
5 |
Correct |
43 ms |
51960 KB |
Output is correct |
6 |
Correct |
44 ms |
51960 KB |
Output is correct |
7 |
Correct |
45 ms |
52088 KB |
Output is correct |
8 |
Correct |
43 ms |
52088 KB |
Output is correct |
9 |
Correct |
43 ms |
52088 KB |
Output is correct |
10 |
Correct |
45 ms |
52088 KB |
Output is correct |
11 |
Correct |
43 ms |
52088 KB |
Output is correct |
12 |
Correct |
45 ms |
52088 KB |
Output is correct |
13 |
Correct |
46 ms |
52088 KB |
Output is correct |
14 |
Correct |
45 ms |
52216 KB |
Output is correct |
15 |
Correct |
45 ms |
52088 KB |
Output is correct |
16 |
Correct |
44 ms |
52088 KB |
Output is correct |
17 |
Correct |
44 ms |
52216 KB |
Output is correct |
18 |
Correct |
44 ms |
52216 KB |
Output is correct |
19 |
Correct |
87 ms |
53880 KB |
Output is correct |
20 |
Correct |
86 ms |
54008 KB |
Output is correct |
21 |
Correct |
97 ms |
54396 KB |
Output is correct |
22 |
Correct |
103 ms |
54776 KB |
Output is correct |
23 |
Correct |
164 ms |
62712 KB |
Output is correct |
24 |
Correct |
204 ms |
65272 KB |
Output is correct |
25 |
Correct |
207 ms |
66424 KB |
Output is correct |
26 |
Correct |
223 ms |
69016 KB |
Output is correct |
27 |
Correct |
43 ms |
51964 KB |
Output is correct |
28 |
Correct |
44 ms |
52136 KB |
Output is correct |
29 |
Correct |
45 ms |
52088 KB |
Output is correct |
30 |
Correct |
61 ms |
52216 KB |
Output is correct |
31 |
Correct |
133 ms |
53112 KB |
Output is correct |
32 |
Correct |
44 ms |
51964 KB |
Output is correct |
33 |
Correct |
44 ms |
52344 KB |
Output is correct |
34 |
Correct |
45 ms |
52344 KB |
Output is correct |
35 |
Correct |
47 ms |
52472 KB |
Output is correct |
36 |
Correct |
73 ms |
52728 KB |
Output is correct |
37 |
Correct |
175 ms |
53756 KB |
Output is correct |
38 |
Correct |
60 ms |
55800 KB |
Output is correct |
39 |
Correct |
62 ms |
55804 KB |
Output is correct |
40 |
Correct |
65 ms |
55800 KB |
Output is correct |
41 |
Correct |
105 ms |
56056 KB |
Output is correct |
42 |
Correct |
242 ms |
57208 KB |
Output is correct |
43 |
Correct |
347 ms |
126060 KB |
Output is correct |
44 |
Correct |
345 ms |
125932 KB |
Output is correct |
45 |
Correct |
356 ms |
126060 KB |
Output is correct |
46 |
Correct |
396 ms |
126036 KB |
Output is correct |
47 |
Correct |
688 ms |
126828 KB |
Output is correct |
48 |
Correct |
62 ms |
54392 KB |
Output is correct |
49 |
Correct |
107 ms |
54520 KB |
Output is correct |
50 |
Correct |
304 ms |
55072 KB |
Output is correct |
51 |
Correct |
534 ms |
55800 KB |
Output is correct |
52 |
Correct |
181 ms |
84856 KB |
Output is correct |
53 |
Correct |
296 ms |
84984 KB |
Output is correct |
54 |
Correct |
760 ms |
86008 KB |
Output is correct |
55 |
Correct |
1406 ms |
86404 KB |
Output is correct |
56 |
Correct |
857 ms |
248072 KB |
Output is correct |
57 |
Correct |
1012 ms |
248324 KB |
Output is correct |
58 |
Correct |
1883 ms |
248652 KB |
Output is correct |
59 |
Correct |
2910 ms |
249140 KB |
Output is correct |
60 |
Correct |
1914 ms |
470648 KB |
Output is correct |
61 |
Correct |
2024 ms |
470532 KB |
Output is correct |
62 |
Correct |
3018 ms |
471044 KB |
Output is correct |
63 |
Correct |
4351 ms |
471424 KB |
Output is correct |
64 |
Execution timed out |
5104 ms |
471008 KB |
Time limit exceeded |