QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62247#4544. Weighted Beautiful TreeqinjianbinAC ✓1448ms87932kbC++172.0kb2022-11-17 18:02:302022-11-17 18:02:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-17 18:02:30]
  • 评测
  • 测评结果:AC
  • 用时:1448ms
  • 内存:87932kb
  • [2022-11-17 18:02:30]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
int c[N], a[N], n;
vector<ll> val[N], dp[N], pre[N], suf[N];
unordered_map<int, int> mp[N];
vector<pair<int, int>> g[N];

void dfs(int u, int fa)
{
	dp[u].resize(val[u].size() + 1);

	for(auto [v, w]: g[u])
	{
		if(v == fa) continue;
		dfs(v, u);

		int pv = mp[v][w];
		ll cur = pre[v][pv];

		int pu = mp[u][w];
		dp[u][pu + 1] += cur;

		cur = suf[v][pv];
		dp[u][0] += cur;
		dp[u][pu] -= cur;

		dp[u][pu] += pre[v][val[v].size() - 1];
		dp[u][pu + 1] -= pre[v][val[v].size() - 1];
	}

//	puts("!!");
//	for(auto x: dp[u]) printf("%lld ", x); puts("");

	rep(i, 1, val[u].size()) dp[u][i] += dp[u][i - 1];
	rep(i, 0, val[u].size()) dp[u][i] += 1LL * c[u] * abs(val[u][i] - a[u]);

	pre[u].resize(val[u].size());
	suf[u].resize(val[u].size());
	pre[u][0] = dp[u][0];
	rep(i, 1, val[u].size()) pre[u][i] = min(dp[u][i], pre[u][i - 1]);

	suf[u][val[u].size() - 1] = dp[u][val[u].size() - 1];
	for(int i = val[u].size() - 2; i >= 0; i--)
	 	suf[u][i] = min(dp[u][i], suf[u][i + 1]);

//	puts("##!");
//	for(auto x: dp[u]) printf("%lld ", x); puts("");
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) scanf("%d", &c[i]), g[i].clear(), val[i].clear(), mp[i].clear(), dp[i].clear(), pre[i].clear(), suf[i].clear();
		_for(i, 1, n) scanf("%d", &a[i]), val[i].push_back(a[i]);
		_for(i, 1, n - 1)
		{
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			g[u].push_back({v, w});
			g[v].push_back({u, w});
			val[u].push_back(w);
			val[v].push_back(w);
		}

		_for(i, 1, n) 
		{
			sort(val[i].begin(), val[i].end());
			rep(j, 0, val[i].size()) mp[i][val[i][j]] = j;
		}

		dfs(1, 0);

		ll ans = 1e18;
		rep(i, 0, dp[1].size() - 1)
			ans = min(ans, dp[1][i]);
		printf("%lld\n", ans);
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1448ms
memory: 87932kb

input:

1000
3
2 1 2
9 9 10
1 2 10
1 3 11
3
1 1 2
9 9 10
1 2 10
1 3 11
99991
914575 436426 979445 648772 690081 933447 190629 703497 47202 407775 894325 963982 804784 968417 302156 631932 735902 895728 78537 723857 330739 286918 329211 539679 238506 63340 686568 361868 660016 287940 296263 224593 601449 836...

output:

3
2
7472540655778111
7473294329562293
8345692029003633
7238550879556940
7841133629861454
4971153421
8181537378
1893424
8143454283
9109290590
11153093754
528748866106540
2081626582
856886106916260
9930470
22231658010804
15244442281704
523150824
0
14045371538269
37592337
45122406677153
184107700398848...

result:

ok 1000 lines