This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
const int maxn = 2e5 + 10, lg = 21;
int n, m;
vector <int> G[maxn];
vector <piii> edge[maxn];
ll dp[maxn], sp[maxn][lg], sum[maxn];
int h[maxn], up[maxn][lg];
int st[maxn], ft[maxn], T;
vector <int> vec[maxn];
void dfs1(int v, int par){
st[v] = T++;
h[v] = h[par] + 1;
up[v][0] = par;
for(int i=1; i<lg; i++)
up[v][i] = up[up[v][i-1]][i-1];
for(int u: G[v]){
if(u == par)
continue;
dfs1(u, v);
}
ft[v] = T;
vec[h[v]].push_back(ft[v]);
}
void dfs(int v, int par){
for(int u: G[v])
sum[v] += sum[u];
}
int lift(int u, int p){
for(int i=lg-1; i>=0; i--)
if(bit(p, i))
u = up[u][i];
return u;
}
int get(int u, int v){
if(h[u] < h[v]) swap(u, v);
u = lift(u, h[u] - h[v]);
if(u == v) return u;
for(int i=lg-1; i>=0; i--)
if(up[u][i] != up[v][i])
u = up[u][i], v = up[v][i];
return up[u][0];
}
int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
cin >> n >> m;
int pi;
for(int i=2; i<=n; i++){
cin >> pi;
G[i].push_back(pi), G[pi].push_back(i);
}
h[0] = -1;
dfs1(1, 0);
int u, v, c;
for(int i=0; i<m; i++){
cin >> u >> v >> c;
int lca = get(u, v);
edge[lca].push_back({{u, v}, c});
}
dfs(1, 0);
cout << dp[1] << '\n';
}
# | 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... |