G题求hack数据

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <math.h>
#include <map>
#include <set> 
#include <queue>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 2e6 + 10, mod = 1e17 + 7;

int n, m;
int a[N];
int h[N], e[N], ne[N], idx;
int dp[N], bk[N], down[N]; //以u为根的最大值 次大值 从根到u的最大值 
int f[N]; // u的父节点编号
int cnt[N];

void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

void dfs(int u, int fa, int w)
{
    down[u] = w + a[u];
    dp[u] = a[u];
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        f[j] = u;
        dfs(j, u, w + a[u]);
        if(dp[j] + a[u] > dp[u]) bk[u] = dp[u], dp[u] = dp[j] + a[u], cnt[u] = 0;
        else if(dp[j] + a[u] > bk[u]) bk[u] = dp[j] + a[u];
        if(dp[j] + a[u] == dp[u]) cnt[u] ++;
    }
    
}

// 记录 以u为根的最大值 次大值 和从根到u的最大值 
//f[u] 表示节点u的父亲是谁
// 把x接到y上 那么能产生的最大价值就是 dp[x] + down[y]
// 如果 dp[x] + down[f[x]] 等于dp[1] 则表示从根经过x到叶子节点的价值为最大值
// 如果最大值唯一， 那么答案一定在根到所有叶子节点的次大价值、x接到y产生的价值,

int query(int x, int y)
{
    int d = dp[x] + down[f[x]]; // 原本的路径
    int ans = dp[x] + down[y]; // 新产生的价值
    
    if(d == dp[1] && cnt[1] == 1) 
    {
        ans = max(ans, bk[1]);
        if(bk[f[x]] == 0) ans = max(ans, down[f[x]]);
        else ans = max(ans, down[f[x]] + bk[f[x]] - a[f[x]]);
    } 
    else 
    {
        ans = max(ans, dp[1]);
    }

    return ans;
}
void solve() 
{
    memset(h, -1, sizeof h);
    
    int Q;
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    for(int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        add(i, x), add(x, i);
    }
    
    dfs(1, -1, 0);
    
    for(int E = 1; E <= Q; E++)
    {
        int x, y;
        cin >> x >>y;
        cout << query(x, y) << endl;
    }
}

//牛客小白---->>>> 97 <<<<----
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) 
    {
        solve();
    }
    return 0;
}