Pagini recente » Cod sursa (job #794899) | Cod sursa (job #2519258) | Cod sursa (job #3125531) | Cod sursa (job #2226022) | Cod sursa (job #2456438)
#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;
}