이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e9 + 10;
vector<int> adj[maxn], query[maxn];
set<pair<int,int>> s[maxn];
int val[maxn], sub[maxn], lazy[maxn], resp[maxn];
void dfs( int cur, int pai ){
sub[cur] = 1;
int sumfilhos = 0;
for( int& viz : adj[cur] ){
if( viz == pai ) continue;
dfs( viz, cur );
sub[cur] += sub[viz];
sumfilhos += resp[viz];
if( adj[cur][0] == pai || sub[viz] > sub[adj[cur][0]] ) swap( viz, adj[cur][0] );
}
if( sub[cur] == 1 ){ for( int x : query[cur] ) s[cur].insert({ x, 0 }); return; }
int big = adj[cur][0];
swap( s[cur], s[big] ); swap( lazy[cur], lazy[big] );
lazy[cur] += sumfilhos - resp[big];
resp[cur] = sumfilhos;
for( int x : query[cur] ){
auto it = s[cur].lower_bound({ x, -inf });
if( it != s[cur].end() && it->first == x ){
resp[cur] = max( resp[cur], ( it->second + lazy[cur] ) + val[x] );
s[cur].erase(it);
}
else s[cur].insert({ x, -lazy[cur] + sumfilhos });
}
for( int viz : adj[cur] ){
if( viz == pai || viz == big ) continue;
for( auto [ x, v ] : s[viz] ){
auto it = s[cur].lower_bound({ x, -inf });
if( it != s[cur].end() && it->first == x ){
resp[cur] = max( resp[cur], ( it->second + lazy[cur] ) + val[x] + ( v + lazy[viz] ) - resp[viz] );
s[cur].erase(it);
}
else s[cur].insert({ x, -lazy[cur] + ( v + lazy[viz] ) + sumfilhos - resp[viz] });
}
}
}
int main(){
int n; cin >> n;
for( int i = 1; i < n; i++ ){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int q; cin >> q;
for( int i = 1; i <= q; i++ ){
int a, b; cin >> a >> b >> val[i];
query[a].push_back(i);
query[b].push_back(i);
}
dfs( 1, 1 );
cout << resp[1];
}
# | 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... |