이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
ll n, W;
int d[maxn], par[maxn], mx_dep=0; ll val[maxn], dp[maxn][3];
vector<pll> gshit[maxn];
vector<int> graph[maxn];
void dfs1(int u, int p) {
mx_dep = max(mx_dep, d[u]);
for(auto &[v, w] : gshit[u]) {
if(v == p) continue;
d[v] = d[u] + 1;
val[v] = w;
par[v] = u;
dfs1(v, u);
}
}
void dfs(int u) {
if(u == 0) return ;
dp[u][0] = dp[u][1] = dp[u][2] = 0;
ll mx1=0, mx2=0;
for(int &v : graph[u]) {
if(v == par[u]) continue;
dp[u][0] = max(dp[u][0], dp[v][0] + val[v]);
dp[u][2] = max(dp[u][2], dp[v][2]);
if(dp[v][0] + val[v] >= mx1) {
mx2 = mx1;
mx1 = dp[v][0] + val[v];
} else if(dp[v][0] + val[v] >= mx2) {
mx2 = dp[v][0] + val[v];
}
}
dp[u][1] = mx1 + mx2;
dp[u][2] = max(dp[u][2], max(dp[u][0], dp[u][1]));
dfs(par[u]);
}
void dfs2(int u, int p) {
ll mx1=0, mx2=0;
for(int &v : graph[u]) {
if(v == p) continue;
dfs2(v, u);
dp[u][0] = max(dp[u][0], dp[v][0] + val[v]);
dp[u][2] = max(dp[u][2], dp[v][2]);
if(dp[v][0] + val[v] >= mx1) {
mx2 = mx1;
mx1 = dp[v][0] + val[v];
} else if(dp[v][0] + val[v] >= mx2) {
mx2 = dp[v][0] + val[v];
}
}
dp[u][1] = mx1 + mx2;
dp[u][2] = max(dp[u][2], max(dp[u][0], dp[u][1]));
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
int q;
cin >> n >> q >> W;
vector<array<ll, 3> > edges;
for(int i=0; i<n-1; i++) {
ll a, b, w;
cin >> a >> b >> w;
edges.push_back({ a, b, w });
gshit[a].push_back({ b, w });
gshit[b].push_back({ a, w });
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs1(1, 1);
for(auto &[a, b, w] : edges) if(d[a] > d[b]) swap(a, b);
if(mx_dep <= 1) {
multiset<ll> ms;
for(auto &[a, b, w] : edges) ms.insert(w);
ll last = 0;
while(q--) {
ll d, e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % W;
ms.erase(ms.find(edges[d][2]));
edges[d][2] = e;
ms.insert(e);
auto it = --ms.end();
ll ans = *it;
if(it != ms.begin()) ans += *(--it);
cout << ans << '\n';
last = ans;
}
return 0;
}
ll last = 0;
dfs2(1, 1);
while(q--) {
ll d, e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % W;
val[edges[d][1]] = e;
dfs(edges[d][0]);
cout << dp[1][2] << '\n';
last = dp[1][2];
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |