Submission #1153886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153886		YSH2020	Sjekira (COCI20_sjekira)	C++20	0 / 110	461 ms	589824 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;

int cost[100005];
vector<int> adj[100005];

set<int> subtree[100005];
int ans;

void dfs(int n, int p) {
  subtree[n].insert(n);
  for (auto i:adj[n]) {
    if (i != p) {
      dfs(i, n);
      auto tmp = subtree[i];
      if (tmp.size() > subtree[n].size()) swap(tmp, subtree[n]);
      for (auto x:tmp) subtree[n].insert(x);
    }
  }
}
set<int> cur_subtree;
void dfs2(int n, int p) {
  for (auto i:adj[n]) {
    if (i != p and cost[i] < cost[n]) {
      //max in that subtree
      auto itr = subtree[i].end();
      itr--;
      ans += *itr+n;
    }
  }
  if (cost[p] < cost[n]) {
    auto itr = cur_subtree.end();
    itr--;
    ans += *itr+n;
  }
  cur_subtree.insert(n);
  for (auto i:adj[n]) {
    if (i != p) {
      dfs2(i, n);
    }
  }
  cur_subtree.erase(n);
}

int main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> cost[i];
  for (int i = 0; i < n-1; i++) {
    int x, y; cin >> x >> y;
    x--; y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  ans = 0;
  dfs(0, -1);
  dfs2(0, -1);
  cout << ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60