#include using namespace std; const int MAXN = (int) 1e5 + 10; const int INF = (int) 1e9; int best_friend[MAXN], money[MAXN], visited[MAXN], on_a_cycle[MAXN]; vector g[MAXN], gr[MAXN], G[MAXN]; // dfs is used for finding one vertex which we are guaranteed that lies in the cycle of current connected component int lastVertex; void dfs(int from) { lastVertex = from; visited[from] = true; for (int i = 0; i < g[from].size(); i++) { int to = g[from][i]; if (!visited[to]) { dfs(to); } } } // visitAll method is simple dfs over undirected graph of the best friend relationships set componentVertices; void visitAll(int from) { componentVertices.insert(from); for (int i = 0; i < G[from].size(); i++) { int to = G[from][i]; if (componentVertices.find(to) == componentVertices.end()) { visitAll(to); } } } long long solve(int from) { vector cycleVertices; long long total = 0; // Firstly process all the vertices lying on a cycle. If you take any one of them, you have to take all of them if (on_a_cycle[from]) { int cur = from; while (!visited[cur]) { cycleVertices.push_back(cur); visited[cur] = true; total += money[cur]; cur = best_friend[cur]; } } else { cycleVertices.push_back(from); total += money[from]; } long long ans = total; // transitions of the dp for (int i = 0; i < cycleVertices.size(); i++) { int from = cycleVertices[i]; for (int j = 0; j < gr[from].size(); j++) { int to = gr[from][j]; long long curProfit = solve(to); if (curProfit > 0) { ans += curProfit; } } } ans = max(ans, 0LL); visited[from] = true; return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T, tc = 0, sum_n = 0; cin >> T; assert(T >= 1 && T <= 100000); while (T--) { tc++; int n; cin >> n; assert(n >= 2 && n <= 100000); sum_n += n; for (int i = 0; i < n; i++) { cin >> best_friend[i]; assert(best_friend[i] >= 1 && best_friend[i] <= n); assert(best_friend[i] != i + 1); best_friend[i]--; } for (int i = 0; i < n; i++) { cin >> money[i]; assert(money[i] >= -INF && money[i] <= INF); } for (int i = 0; i < n; i++) { g[i].clear(); gr[i].clear(); G[i].clear(); visited[i] = false; on_a_cycle[i] = false; } for (int i = 0; i < n; i++) { g[i].push_back(best_friend[i]); gr[best_friend[i]].push_back(i); G[i].push_back(best_friend[i]); G[best_friend[i]].push_back(i); } // check whether a vertex on cycle (a cycle is collection of two or more vertices) for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(i); on_a_cycle[lastVertex] = true; componentVertices.clear(); visitAll(lastVertex); for (set :: iterator it = componentVertices.begin(); it != componentVertices.end(); it++) { visited[*it] = true; } } } // now compute all the vertices lying in a cycle in each component for (int i = 0; i < n; i++) { visited[i] = false; } for (int i = 0; i < n; i++) { if (on_a_cycle[i]) { int from = i; while (!visited[from]) { visited[from] = true; on_a_cycle[from] = true; from = best_friend[from]; } } } // get maximum profit in a single component and sum up the quantity for all for (int i = 0; i < n; i++) { visited[i] = 0; } long long ans = 0; for (int i = 0; i < n; i++) { if (!visited[i] && on_a_cycle[i]) { long long cur_ans = solve(i); ans += cur_ans; } } for (int i = 0; i < n; i++) { assert(visited[i]); } cout << ans << endl; } assert(sum_n >= 1 && sum_n <= (int) 1e6); return 0; }