제출 #1332910

#제출 시각아이디문제언어결과실행 시간메모리
1332910neptunnsHarmonija (COCI25_harmonija)C++20
0 / 110
309 ms706560 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define maxn 100005
#define mi LLONG_MIN
#define ma LLONG_MAX
#define mod 1000000007
#define pb push_back
#define S second
#define F first
int n, q;
const int K = 18;
int up[K][maxn], d[maxn];
struct mat
{
    int m[5][5];
    mat()
    {
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                m[i][j] = -1e18;
            }
        }
    }
};
mat merge(mat a, mat b)
{
    mat c;
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            for (int k = 0; k < 5; k++)
            {
                c.m[i][j] = max(c.m[i][j], a.m[i][k] + b.m[k][j]);
            }
        }
    }
    return c;
}
mat mup[K][maxn], mdown[K][maxn];
vector<int> g[maxn], r(maxn), b(maxn);

void dfs(int u = 0, int p = 0, int dep = 0)
{
    stack<int> st;
    st.push(u);
    d[u] = dep;
    up[0][u] = p;
    mat matr;
    matr.m[1][0] = r[u];
    matr.m[2][1] = r[u];
    matr.m[0][1] = b[u];
    matr.m[1][2] = b[u];
    matr.m[3][2] = r[u];
    matr.m[2][3] = b[u];
    matr.m[4][3] = r[u];
    matr.m[3][4] = b[u];
    mup[0][u] = matr;
    mdown[0][u] = matr;
    while (!st.empty())
    {
        int v = st.top();
        st.pop();
        for (int it : g[v])
        {
            if (it == up[0][v])
                continue;
            up[0][it] = v;
            d[it] = d[v] + 1;
            mat matre;
            matre.m[1][0] = r[it];
            matre.m[2][1] = r[it];
            matre.m[0][1] = b[it];
            matre.m[1][2] = b[it];
            matre.m[3][2] = r[it];
            matre.m[2][3] = b[it];
            matre.m[4][3] = r[it];
            matre.m[3][4] = b[it];
            mup[0][it] = matre;
            mdown[0][it] = matre;
            st.push(it);
        }
    }
}
int get(int u, int v)
{
    if (d[u] < d[v])
        swap(u, v);
    for (int i = K - 1; i >= 0; i--)
    {
        if (d[u] - (1 << i) >= d[v])
            u = up[i][u];
    }
    if (u == v)
        return u;
    for (int i = K - 1; i >= 0; i--)
    {
        if (up[i][u] != up[i][v])
        {
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> r[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs();
    for (int i = 1; i < K; i++)
    {
        for (int j = 0; j < n; j++)
        {
            up[i][j] = up[i - 1][up[i - 1][j]];
            mup[i][j] = merge(mup[i - 1][j], mup[i - 1][up[i - 1][j]]);
            mdown[i][j] = merge(mdown[i - 1][up[i - 1][j]], mdown[i - 1][j]);
        }
    }

    while (q--)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        int lca = get(u, v);
        mat U;
        for (int i = 0; i < 5; i++)
            U.m[i][i] = 0;
        int c = u;
        for (int i = K - 1; i >= 0; i--)
        {
            if (d[c] - (1 << i) >= d[lca])
            {
                U = merge(U, mup[i][c]);
                c = up[i][c];
            }
        }

        mat V;
        for (int i = 0; i < 5; i++)
            V.m[i][i] = 0;
        c = v;
        for (int i = K - 1; i >= 0; i--)
        {
            if (d[c] - (1 << i) > d[lca])
            {
                V = merge(mdown[i][c], V);
                c = up[i][c];
            }
        }
        mat an = merge(U, V);
        int ans = mi;
        for (int i = 0; i < 5; i++)
        {
            ans = max(ans, an.m[2][i]);
        }
        cout << ans << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...