Submission #1173273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173273		Nurislam	Construction of Highway (JOI18_construction)	C++20	0 / 100	3 ms	5956 KiB

construction

#include <bits/stdc++.h>

using namespace std;


#define int long long
//#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

struct bitt {
	vector<int> t;
	int n;
	bitt (int N) : n(N+1) {
		t.resize(n+2);
	};
	
	void upd(int i, int va) { i ++ ;
		for(; i < n; i += (i & -i)) t[i] += va;
	};
	
	int get(int i) { i ++ ;
		int res = 0;
		for(; i > 0; i -= (i & -i)) res += t[i];
		return res;
	};
	
	int get(int l, int r) { r--;
		return get(r ) - get( -- l );
	};
}bt(N);


vector<vector<int>> g(N);
vector<vector<array<int,2>>> lst(N);

int sz[N], pr[N], head[N], heavy[N], dep[N], id[N];
int tim = 1;

void dfs(int ps, int par) {
	sz[ps] = 1;
	pr[ps] = par;
	heavy[ps] = 0;
	
	for(int to : g[ps]) {
		if(to == par)continue;
		dep[to] = dep[ps] + 1;
		dfs(to, ps);
		sz[ps] += sz[to];
		if(sz[heavy[ps]] < sz[to]) heavy[ps] = to;
	}
}

void hld(int ps, int hd) {
	head[ps] = hd;
	id[ps] = tim ++ ;
	
	if(heavy[ps])
		hld(heavy[ps], hd);
		
	for(int to : g[ps]){
		if(to == pr[ps] || to == heavy[ps])continue;
		hld(to, to);
	}
};


int query(int ps) {
	vector<array<int,2>> ord;
	
	while(1) {
		int to = head[ps];
		int ds = dep[ps] - dep[to] + 1;
		
		vector<array<int,2>> res;
		int la = 0;
		for(int i = lst[to].size()-1; i >= 0; i -- ) {
			auto [x, y] = lst[to][i];
			res.push_back({x, y-la});
			la = y;
			if(y >= ds) break;
		}
		reverse(res.begin(), res.end());
		for(auto i : res)ord.push_back(i);
		
		if(to == 1) break;
		ps = pr[to];
	}
	
	int ans = 0;
	for(auto [x, y] : ord) {
		ans += bt.get(x-1) * y;
		bt.upd(x, y);
	}
	for(auto [x, y] : ord) bt.upd(x, -y);
	return ans;
};

void upd (int ps, int va) {
	while(1) {
		int to = head[ps];
		int ds = dep[ps] - dep[to] + 1;
		
		while(lst[to].size() && lst[to].back()[1] <= ds)lst[to].pop_back();
		lst[to].push_back({va, ds});
		
		if(to == 1)return;
		ps = pr[to];
	}
};


void solve(){
	int n; cin >> n;
	
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++ )cin >> a[i];
	
	vector<int> b = a;
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for(int i = 1; i <= n; i ++ )a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
	
	vector<array<int,2>> ed(n-1);
	for(auto &[a, b] : ed) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1, 1);
	hld(1, 1);
	
	
	lst[1].push_back({a[1], 1});
	for(auto [u, v] : ed) {
		cout << query(u) << '\n';
		upd(v, a[v]);
	};
	
};



signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

• Subtask 1: 0 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84