B. Apple Tree 暴力 + 数学

​​http://codeforces.com/problemset/problem/348/B​​

注意到如果顶点的数值确定了，那么它分下去的个数也就确定了，那么可以暴力枚举顶点的数值。

顶点的数值是和LCM相隔的，LCM就是，比如1有三个子节点，那么1的数值起码都是3的倍数，不然不能整除。

同理，1有三个儿子2、3、4、，如果3有三个儿子，那么1就要起码是9的倍数了，因为需要分给3的时候至少是3.

所以算出整颗树的LCM，叶子节点LCM是1，其他的LCM = lcm(所有子节点) * son[cur]

算出这个后，就可以暴力枚举顶点1的值了，每次枚举都dfs一次，有点暴力1700ms，学学正解先。

注意一点的就是LCM会爆LL，这个时候直接输出sum即可

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e5 + 20;
int a[maxn];
LL sum;
struct Node {
    int u, v, tonext;
}e[maxn * 2];
int first[maxn], num;
void addEdge(int u, int v) {
    ++num;
    e[num].u = u, e[num].v = v, e[num].tonext = first[u];
    first[u] = num;
}
int vis[maxn], DFN = 1;
int son[maxn];
void findSon(int cur) {
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v] == DFN) continue;
        vis[v] = DFN;
        son[cur]++;
        findSon(v);
    }
}
LL ans = 1e18L, tans;
LL LCM;
LL lcm(LL a, LL b) {
    return a / __gcd(a, b) * b;
}
bool flag;
void dfs(int cur, LL val) {
    if (flag) return;
    if (son[cur] == 0) {
        if (val > a[cur]) {
            flag = true;
            return;
        }
        tans += a[cur] - val;
        return;
    }
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v] == DFN) continue;
        vis[v] = DFN;
        if (val % son[cur] != 0) {
            flag = true;
            return;
        }
        dfs(v, val / son[cur]);
    }
}
LL calc(int cur) {
    if (son[cur] == 0) return 1;
    LL thisLCM = 1;
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v] == DFN) continue;
        vis[v] = DFN;
        thisLCM = lcm(thisLCM, calc(v));
    }
    if (thisLCM > sum / son[cur]) {
        printf("%I64d\n", sum);
        exit(0);
    }
    return son[cur] * thisLCM;
}
void work() {
    int n;
    scanf("%d", &n);
    LCM = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    for (int i = 1; i <= n - 1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    vis[1] = DFN;
    findSon(1);
    ++DFN;
    vis[1] = DFN;
    LCM = calc(1);
//    cout << LCM << endl;
    ans = sum;
    sum /= LCM;
    sum *= LCM;
    for (LL i = sum; i >= LCM; i -= LCM) {
        ++DFN, tans = 0;
        flag = false;
//        dfs(1, 24);
        vis[1] = DFN;
        dfs(1, i);
        if (flag) continue;
        printf("%I64d\n", ans - i);
        return;
    }
    printf("%I64d\n", ans);
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code

因为已经知道根节点的值是LCM、2 * LCM、3 * LCM、..... sum中合法的最大的哪一个，那么可以二分答案。

一开始想把她们全部存入vector再二分，但是发现不用，直接二分id就行，就是二分LCM上面的那个倍数就可以了。

500ms

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e5 + 20;
int a[maxn];
LL sum;
struct Node {
    int u, v, tonext;
}e[maxn * 2];
int first[maxn], num;
void addEdge(int u, int v) {
    ++num;
    e[num].u = u, e[num].v = v, e[num].tonext = first[u];
    first[u] = num;
}
int vis[maxn], DFN = 1;
int son[maxn];
void findSon(int cur) {
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v] == DFN) continue;
        vis[v] = DFN;
        son[cur]++;
        findSon(v);
    }
}
LL ans = 1e18L, tans;
LL LCM;
LL lcm(LL a, LL b) {
    return a / __gcd(a, b) * b;
}
bool flag;
void dfs(int cur, LL val) {
    if (flag) return;
    if (son[cur] == 0) {
        if (val > a[cur]) {
            flag = true;
            return;
        }
        tans += a[cur] - val;
        return;
    }
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v] == DFN) continue;
        vis[v] = DFN;
        if (val % son[cur] != 0) {
            flag = true;
            return;
        }
        dfs(v, val / son[cur]);
    }
}
LL calc(int cur) {
    if (son[cur] == 0) return 1;
    LL thisLCM = 1;
    for (int i = first[cur]; i; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v] == DFN) continue;
        vis[v] = DFN;
        thisLCM = lcm(thisLCM, calc(v));
    }
    if (thisLCM > sum / son[cur]) {
        printf("%I64d\n", sum);
        exit(0);
    }
    return son[cur] * thisLCM;
}
void work() {
    int n;
    scanf("%d", &n);
    LCM = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    for (int i = 1; i <= n - 1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    vis[1] = DFN;
    findSon(1);
    ++DFN;
    vis[1] = DFN;
    LCM = calc(1);
//    cout << LCM << endl;
    ans = sum;
    sum /= LCM;
    sum *= LCM;
    LL be = 0, en = sum / LCM;
    while (be <= en) {
        LL mid = ((be + en) >> 1);
        ++DFN, flag = false;
        vis[1] = DFN;
        dfs(1, mid * LCM);
        if (flag) {
            en = mid - 1;
        } else be = mid + 1;
    }
    cout << ans - LCM * en << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code