Cod sursa(job #2607112)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 29 aprilie 2020 11:49:42
Problema Guvern Scor 100
Compilator cpp-64 Status done
Runda why Marime 2.6 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

struct Interval {
  int l, r, c;
  bool operator <(const Interval& other) const {
    return r < other.r;
  }
} a[MAXN];

int n;
vector<int>G[MAXN];
int v[MAXN];
set<pair<int, int> >s;
vector<int>up[MAXN];
int l[MAXN], r[MAXN], k;
int dp[MAXN];
int aib[MAXN];

void update(int pos, int val) {
  for (; pos <= n; pos += (pos &- pos))
    aib[pos] = max(aib[pos], val);
}

int query(int pos) {
  int ans = 0;
  for (; pos; pos -= (pos & -pos))
    ans = max(ans, aib[pos]);
  return ans;
}

void res(int pos) {
  for (; pos <= n; pos += (pos & -pos))
    aib[pos] = 0;
}

void dfs(int node, int papa) {
  l[node] = ++k;
  if (node != 0)
    up[(*s.lower_bound({v[node], 0})).second].push_back(node);
  s.insert({v[node], node});
  for (auto it:G[node])
    if (it != papa)
      dfs(it, node);
  int m = 0;
  /*cerr << node << ':';
  for (auto it:up[node]) {
    cerr << it << ' ';
  }
  cerr << '\n';*/
  for (auto it:up[node])
    a[++m] = {l[it], r[it], dp[it]};
  sort(a + 1, a + m + 1);
  for (int i = 1; i <= m; ++i) {
     int val = query(a[i].l - 1) + a[i].c;
     dp[node] = max(dp[node], val);
     update(a[i].r, val);
  }
  for (int i = 1; i <= m; ++i)
    res(a[i].r);
  dp[node]++;
  s.erase(s.find({v[node], node}));
  r[node] = k;
}


class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
} in ("guvern.in");

int main() {
  freopen("guvern.out", "w", stdout);

  in >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    in >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  G[0].push_back(1);

  v[0] = 2e9;
  for (int i = 1; i <= n; ++i)
    in >> v[i];

  dfs(0, 0);

  printf("%d\n", dp[0] - 1);

  return 0;
}