QBXT 4242.小葱拿糖

统计五个数组，\(v_i\) \(i\)点的美味值（权值），f_i 当前节点到根节点的权值和，\(m_{i,0/1}\) i 的最大/次大向下走的路径权值和（不包括点 \(i\) ），\(g_{i,0/1}\) 从 i 点向上走的，或者走其他子树的最大路径（0/1 = 包含/不包含 \(m_{i,0}\)）。\(st_i\) i 在不在 fa 的 \(m_{i,0}\) 上。

其中除了 g 都易得，而 g 可以通过在树上递推，递推出来，递推式子为：
g[u][0] = max(g[fa][st[u]], m[u][0]) + v[u];
g[u][1] = max(g[fa][st[u]], m[u][1]) + v[u];
为了省时间就直接给代码了，fa 是 u 的父节点。可以想想怎么出来的

主要分为 4 种。

1. p,q 都不是 LCA。这种 pq 之间路径易得，为 \(f_p + f_q - 2f_{lca} + v_{lca}\), 而在 q 点还能往下走任意子树路径，即加上 \(m_{i,0}\)。即：f[i] + f[j] - 2 * f[p] + v[p] + m[j][0]
2. p 是 LCA，那么 q 在 p 下方，\(m_{i,0}\) 一定可以取到，即f[j] - f[i] + v[i] + m[j][0]
3. q 是 LCA，此时向上取，即使用 g 数组，为 f[i] - f[j] + g[j][st[k]]
4. p,q 相等 即向上或者向下走，即 max(m[i][0] + v[i], g[i][0])

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int N = 100010, M = N * 2;

int n, mk;
int h[N], e[M], ne[M], w[M], idx;
int f[N], g[N][2], m[N][2]; // m不算i本身 g含本身
bool st[N];
int depth[N], fa[N][20];
int v[N];

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

void dfs1(int u, int fas)
{
    depth[u] = depth[fas] + 1;
    fa[u][0] = fas;
    for (int i = 1; i <= 17; i ++ )
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    f[u] += v[u] + f[fas];
    int last = -1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (fas == j) continue;
        dfs1(j, u);
        if (m[j][0] + v[j] > m[u][0] || last == -1)
        {
            m[u][1] = m[u][0];
            m[u][0] = m[j][0] + v[j];
            st[j] = true;
            st[last] = false;
            last = j;
        }
        else if (m[j][0] > m[u][1])
        {
            m[u][1] = m[j][0] + v[j]; 
        }
    }
}

void dfs2(int u, int fa)
{
    g[u][0] = max(g[fa][st[u]], m[u][0]) + v[u];
    g[u][1] = max(g[fa][st[u]], m[u][1]) + v[u];
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (fa == j) continue;
        dfs2(j, u);
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    
    for (int i = 17; i >= 0; i -- )
        if (depth[fa[a][i]] >= depth[b])
            a = fa[a][i];
            
    if (a == b) return b;
    
    for (int i = 17; i >= 0; i -- )
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    return fa[a][0];
}

int main()
{
//     freopen("take.in","r",stdin);
// 	freopen("take.out","w",stdout);
    cin >> n >> mk;
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    
    
    dfs1(1, 0);
    dfs2(1, 0);
    
    
    while (mk -- )
    {
        int i, j, sum = 0;
        scanf("%d%d", &i, &j);
        int p = lca(i, j);
        
        if (i == j) sum = max(m[i][0] + v[i], g[i][0]);
        else if (p == i)
        {
            sum = f[j] - f[i] + v[i] + m[j][0];
        }
        else if (p == j)
        {
            int k = i; // 用于判断是否占用了 m0
            for (int i = 17; i >= 0; i -- )
            {
                if (depth[fa[k][i]] > depth[j])
                    k = fa[k][i];
            }
            sum = f[i] - f[j] + g[j][st[k]];
        }
        else 
        {
            sum = f[i] + f[j] - 2 * f[p] + v[p] + m[j][0];
        }
        printf("%d\n", sum);
    }
    
    
    return 0;
}