#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, p[maxn];
ll w[maxn];
void input()
{
cin >> n;
for (int i = 2; i <= n; i ++)
cin >> p[i];
for (int i = 2; i <= n; i ++)
cin >> w[i];
}
vector < pair < int, ll > > adj[maxn];
int tin[maxn], occ[2 * maxn], timer;
ll depth[maxn];
void traverse(int v)
{
tin[v] = ++ timer;
occ[timer] = v;
for (pair < int, ll > nb : adj[v])
{
depth[nb.first] = depth[v] + nb.second;
traverse(nb.first);
occ[++ timer] = v;
}
}
const int maxlog = 21;
int dp[maxlog][2 * maxn], lg[2 * maxn];
void sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = occ[i];
}
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int get_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1, lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
ll dist(int v, int u)
{
int lca = get_lca(v, u);
return depth[v] + depth[u] - 2 * depth[lca];
}
void init_tree()
{
for (int i = 2; i <= n; i ++)
{
adj[p[i]].push_back({i, w[i]});
}
traverse(1);
}
bool cmp_tin(int a, int b)
{
return tin[a] < tin[b];
}
vector < pair < int, ll > > vir_adj[maxn];
void clear_vir_tree(vector < int > st)
{
for (int v : st)
vir_adj[v].clear();
}
ll virtual_tree(vector < int > ver_st)
{
sort(ver_st.begin(), ver_st.end(), cmp_tin); /// sort by dfs in time
int sz = ver_st.size();
for (int i = 1; i < sz; i ++)
{
st.push_back(get_lca(ver_st[i], ver_st[i - 1])); /// mark the additional vertices
}
sort(ver_st.begin(), ver_st.end(), cmp_tin); /// sort with additional
vector < int > marked; /// contains marked vertices
marked.push_back(ver_st[0]);
for (int i = 1; i < st.size(); i ++)
if (ver_st[i] != ver_st[i - 1]) /// remove duplicates
marked.push_back(ver_st[i]);
/// there is a function unique to do this
/// but I hate it
stack < int > st;
int root = marked[0];
st.push(root);
for (int i = 1; i < marked.size(); i ++)
{
while(get_lca(st.top() && marked[i]) != st.top()) /// st can never be empty
st.pop(); /// removing all vertexes from which we have gone up
vir_adj[st.top()].push_back({marked[i], depth[marked[i]] - depth[st.top()]});
/// adds edge from the parent of marked[i] to marked[i]
/// edges on the path are compressed
}
/// solve query
clear_vir_tree(marked);
}
void answer_queries()
{
}
void clear_data()
{
for (int i = 1; i <= n; i ++)
{
adj[i].clear();
}
timer = 0;
}
void solve()
{
input();
init_tree();
sparse_table();
answer_queries();
clear_data();
}
int main()
{
int t;
cin >> t;
while(t --)
solve();
return 0;
}
Compilation message
minerals.cpp: In function 'll virtual_tree(std::vector<int>)':
minerals.cpp:104:9: error: 'st' was not declared in this scope; did you mean 'sz'?
104 | st.push_back(get_lca(ver_st[i], ver_st[i - 1])); /// mark the additional vertices
| ^~
| sz
minerals.cpp:111:25: error: 'st' was not declared in this scope; did you mean 'sz'?
111 | for (int i = 1; i < st.size(); i ++)
| ^~
| sz
minerals.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i = 1; i < marked.size(); i ++)
| ~~^~~~~~~~~~~~~~~
minerals.cpp:122:44: error: too few arguments to function 'int get_lca(int, int)'
122 | while(get_lca(st.top() && marked[i]) != st.top()) /// st can never be empty
| ^
minerals.cpp:58:5: note: declared here
58 | int get_lca(int v, int u)
| ^~~~~~~
minerals.cpp:134:1: warning: no return statement in function returning non-void [-Wreturn-type]
134 | }
| ^
