348B - Apple Tree https://codeforces.com/problemset/problem/348/B
我们设最后答案为 x , 我们我们就能用 x 表示出所有节点下面的苹果个数, 然后用叶子节点求 lcm, 取最大的可行解.
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define PLL pair<LL, LL>
- #define PLI pair<LL, int>
- #define PII pair<int, int>
- #define SZ(x) ((int)x.size())
- #define ull unsigned long long
- using namespace std;
- const int N = 1e5 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = 1e9 + 7;
- const double eps = 1e-8;
- int n, a[N];
- LL dv[N], sum[N], all;
- vector<int> leaf;
- vector<int> G[N];
- void solve(int u, int fa) {
- if(u != 1 && SZ(G[u]) == 1) leaf.push_back(u);
- sum[u] = a[u];
- for(int v : G[u]) {
- if(v == fa) continue;
- solve(v, u);
- sum[u] += sum[v];
- }
- }
- void dfs(int u, int fa) {
- if(dv[u]> all) {
- printf("%lld\n", all);
- exit(0);
- }
- for(int v : G[u]) {
- if(v == fa) continue;
- if(u == 1) dv[v] = dv[u] * SZ(G[u]);
- else dv[v] = dv[u] * (SZ(G[u]) - 1);
- dfs(v, u);
- }
- }
- bool check(LL x) {
- for(auto& id : leaf) {
- if(x / dv[id]> a[id]) return false;
- }
- return true;
- }
- int main() {
- scanf("%d", &n);
- for(int i = 1; i <= n; i++) scanf("%d", &a[i]), all += a[i];
- for(int i = 1; i <n; i++) {
- int u, v; scanf("%d%d", &u, &v);
- G[u].push_back(v);
- G[v].push_back(u);
- }
- dv[1] = 1;
- solve(1, 0);
- dfs(1, 0);
- LL lcm = 1;
- for(auto& id : leaf) {
- LL gcd = __gcd(lcm, dv[id]);
- if(1.0 * lcm / gcd * dv[id]> all) {
- printf("%lld\n", all);
- return 0;
- }
- lcm = lcm / gcd * dv[id];
- }
- LL low = 1, high = all / lcm, ans = 0;
- while(low <= high) {
- LL mid = low + high>> 1;
- if(check(mid * lcm)) ans = mid, low = mid + 1;
- else high = mid - 1;
- }
- printf("%lld\n", all - ans * lcm);
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2944824.html