제출 #1355700

#제출 시각아이디문제언어결과실행 시간메모리
1355700marcogambaroTree (IOI24_tree)C++20
18 / 100
49 ms26896 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull long long
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define all(x) x.begin(), x.end()
#define fi first 
#define se second 
#ifdef MARCO
#define infof(str,...) do{ fprintf(stderr, str"\n", ##__VA_ARGS__);} while(0)
#define infor(str,...) do{ fprintf(stderr, str, #__VA_ARGS__);} while(0)
#else 
#define infof(str,...)
#define infor(str,...)
#endif

vector<vector<int>> G;
int N;
vector<int> W;
vector<int> tin, tout;

ll leafw, leafn;

void gett(int v) {
	static int tt = 0;
	tin[v] = tt++;
	for(auto &u: G[v]) {
		gett(u);
	}
	tout[v] = tt;
}

vector<ll> p, sfx;

int dfs(int v) {
	if(G[v].empty()) return 1;

	int k = 0;
	for(auto &u: G[v]) {
		k += dfs(u);
		if(W[v] == 0) {
			p.push_back(k);
			k = 0;
		}
	}

	if(W[v] == 0) return 1;
	else return k;
}


void init(std::vector<int> P, std::vector<int> W) {
	N = P.size();
	
	G.resize(N);	

	for(int i=1; i<N; i++) {
		G[P[i]].emplace_back(i);
	}
	for(int i=0; i<N; i++) {
		if(G[i].empty()) leafw+=W[i], leafn++;
	}

	tin = tout = vector<int>(N);
	gett(0);
	
	::W.swap(W);
	p.push_back(dfs(0));

	sort(all(p));
	sfx = vector<ll>(p.size());
	sfx.back() = p.back();
	for(int i=sfx.size()-2; i>-1; i--)
		sfx[i] = sfx[i+1]+p[i];
	sfx.push_back(0);
}

long long query(int L, int R) {
	int x = upper_bound(all(p), R/L)-p.begin();

	return sfx[x]*L - (ll)R*(p.size()-x) + L*leafw;
}


#ifdef MARCO
int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> P(N);
  P[0] = -1;
  for (int i = 1; i < N; i++)
    assert(1 == scanf("%d", &P[i]));
  std::vector<int> W(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &W[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; j++)
    assert(2 == scanf("%d%d", &L[j], &R[j]));
  fclose(stdin);


  init(P, W);
  std::vector<long long> A(Q);
  for (int j = 0; j < Q; j++)
    A[j] = query(L[j], R[j]);

  for (int j = 0; j < Q; j++)
    printf("%lld\n", A[j]);
  fclose(stdout);

  return 0;
}
#endif
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...