//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(ll x = 1 ; x <= y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
const int nmax = 100005;
const ll linf = 1e17;
const ll mod = 1e9+7;
const int inf = 1e9+7;
const ll lim = 1e4;
int n,m;
vec <int> g[nmax];
int tin[nmax], tout[nmax],tt=1;
int up[nmax][20];
vec < pair < pii , ll > > pth[nmax];
vec < int > vc;
void dfs(int nod, int par){
up[nod][0] = par;
tin[nod] = ++tt;
for(int j : g[nod]){
if(j != par)
dfs(j,nod);
}
tout[nod] = ++tt;
}
bool anc(int a, int b){
return ( tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
if(anc(a,b))return a;
int p = a;
for(int i = 16 ; i >= 0; i--){
if(!anc(up[p][i],b)) p = up[p][i];
}
return up[p][0];
}
struct {
ll bit[2*nmax];
ll query(int pos){
ll r = 0;
for(;pos > 0; pos -= pos&-pos){
r += bit[pos];
}
return r;
}
void update(int pos , int val){
for(;pos <= tt ; pos += pos&-pos){
bit[pos] += val;
}
}
ll range_query(int l , int r){
return query(r) - query(l-1);
}
}bt1,bt2;
ll dp[nmax];
void dfs2(int nod, int par){
for(int j : g[nod]){
if(j != par)
dfs2(j,nod);
}
ll r = 0;
for(int j : g[nod]){
if(j == par)continue;
r += dp[j];
}
ll rez = r;
bt1.update(tin[nod],r);
bt2.update(tout[nod],r);
for(auto path : pth[nod]){
rez = max( rez, bt1.range_query(tin[nod],tin[path.fr.fr]) - bt2.range_query(tin[nod],tin[path.fr.fr])
+bt1.range_query(tin[nod],tin[path.fr.sc]) - bt2.range_query(tin[nod],tin[path.fr.sc]) - r + path.sc );
}
dp[nod] = rez;
bt1.update(tin[nod],-dp[nod]);
bt2.update(tout[nod],-dp[nod]);
cout << nod << ' ' << dp[nod] << '\n';
}
int main(){
fast;
cin >> n;
forn(i,n-1){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1,1);
for(int i = 1 ; i < 20 ; i++){
forn(ii,n){
up[ii][i] = up[up[ii][i-1]][i-1];
}
}
cin >> m;
forn(i,m){
int a, b, c;
cin >> a >> b >> c;
pth[lca(a,b)].pb({{a,b},c});
}
dfs2(1,1);
cout << dp[1] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
23640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
