Cod sursa(job #2456438)

Utilizator Coroian_DavidCoroian David Coroian_David Data 14 septembrie 2019 13:10:22
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda teme_upb Marime 2.94 kb
#include <bits/stdc++.h>

#define MAX_N 250000
#define MAX_M 500000

#define xx first
#define yy second

using namespace std;

int rez[MAX_M + 1];

vector <int> g[MAX_N + 1];

int n, q;
int v[MAX_N + 1];

deque <int> dp[MAX_N + 1];
int poz[MAX_N + 1];
int K;
int sum[MAX_N + 1];

vector <pair<int, int>> qr[MAX_N + 1];

void add(int a, int b)
{
    g[a].push_back(b);
}

void readFile()
{
    ifstream f("arb.in");

    f >> n;
    for(int i = 1; i <= n; i ++)
        f >> v[i];

    for(int i = 2; i <= n; i ++)
    {
        int a;
        f >> a;
        //f.flush();
        add(a, i);
        add(i, a);
    }

    f >> q;
    for(int i = 1; i <= q; i ++)
    {
        int a, b;
        f >> a >> b;
        qr[a].push_back({b, i});
    }

   // cout << sizeof(f) /1024.0D/1024.0D << "+++\n";
    f.close();
}

int smen[MAX_N + 1];

void comb(int a, int b)
{
    for(int i = 0; i <= dp[b].size(); i ++)
    {
        smen[i] = 0;

        if(i < dp[b].size())
            dp[b][i] += sum[b];
    }
    sum[b] = 0;

    for(int i = 0; i < dp[b].size(); i ++)
    {
        sum[a] += dp[b][i];

        smen[0] -= dp[b][i];
        smen[i + 1] += dp[b][i];
    }

    for(int i = 0; i <= dp[b].size(); i ++)
    {
        if(i > 0)
            smen[i] += smen[i - 1];

        dp[a][i] += smen[i];
    }
}

void dfs(int a, int tata)
{
    int fiu = 0, mx = 0;
    for(auto u : g[a])
    {
        if(u != tata)
        {
            dfs(u, a);
            if(dp[poz[u]].size() > mx)
            {
                mx = dp[poz[u]].size();
                fiu = u;
            }
        }
    }

    if(fiu == 0)
    {
        ++ K;
        poz[a] = K;
        dp[poz[a]].push_back(v[a]);
        sum[poz[a]] = 0;

        return;
    }

    poz[a] = poz[fiu];
    dp[poz[a]].push_front(-sum[poz[a]]);
    sum[poz[a]] += v[a];

    //cout << sum[poz[a]] << "+++\n";

    for(auto u : g[a])
    {
        if(u != tata && u != fiu)
            comb(poz[a], poz[u]);
    }

    for(auto u : qr[a])
        rez[u.yy] = dp[poz[a]][u.xx] + sum[poz[a]];
/*
    cout << "PENUTR " << a << " " << sum[poz[a]] << "\n";
    for(auto u : dp[poz[a]])
        cout << u + sum[poz[a]] << " ";
    cout << "\n";*/
}

void solve()
{
    dfs(1, -1);
}

void printFile()
{
    FILE *g = fopen("arb.out", "w");

    for(int i = 1; i <= q; i ++)
    fprintf(g, "%d\n", rez[i]); //   g << rez[i] << "\n";
/*
        srand(time(0));
    g << "250000\n";
    for(int i = 1; i <= 250000; i ++)
        g << rand() %  5001 << " ";
    g << "\n";
    for(int i = 2; i <= 250000; i ++)
    g << rand() % 250000 + 1 << " ";
    g << "\n";
    g << "500000\n";
    for(int i = 1; i <= 500000; i ++)
        g << rand() % 250000 + 1 << " " << 0 << "\n";
*/
   // g.close();

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

   // cout << (sizeof(dp) + sizeof(qr) + sizeof(g) + 4 * n * 2 + 2 * 4 * q + n * 8 + sizeof(sum)+sizeof(poz)+sizeof(rez)+sizeof(smen)+sizeof(v)) / 1024.0D/1024.0D;

    return 0;
}