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 + ;

int a[maxn];

LL sum;

struct Node {

    int u, v, tonext;

}e[maxn * ];

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 = ;

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] == ) {

        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] != ) {

            flag = true;

            return;

        }

        dfs(v, val / son[cur]);

    }

}

LL calc(int cur) {

    if (son[cur] == ) return ;

    LL thisLCM = ;

    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();

    }

    return son[cur] * thisLCM;

}

void work() {

    int n;

    scanf("%d", &n);

    LCM = ;

    for (int i = ; i <= n; ++i) {

        scanf("%d", &a[i]);

        sum += a[i];

    }

    for (int i = ; i <= n - ; ++i) {

        int u, v;

        scanf("%d%d", &u, &v);

        addEdge(u, v);

        addEdge(v, u);

    }

    vis[] = DFN;

    findSon();

    ++DFN;

    vis[] = DFN;

    LCM = calc();

//    cout << LCM << endl;

    ans = sum;

    sum /= LCM;

    sum *= LCM;

    for (LL i = sum; i >= LCM; i -= LCM) {

        ++DFN, tans = ;

        flag = false;

//        dfs(1, 24);

        vis[] = DFN;

        dfs(, 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 ;

}

因为已经知道根节点的值是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 + ;

int a[maxn];

LL sum;

struct Node {

    int u, v, tonext;

}e[maxn * ];

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 = ;

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] == ) {

        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] != ) {

            flag = true;

            return;

        }

        dfs(v, val / son[cur]);

    }

}

LL calc(int cur) {

    if (son[cur] == ) return ;

    LL thisLCM = ;

    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();

    }

    return son[cur] * thisLCM;

}

void work() {

    int n;

    scanf("%d", &n);

    LCM = ;

    for (int i = ; i <= n; ++i) {

        scanf("%d", &a[i]);

        sum += a[i];

    }

    for (int i = ; i <= n - ; ++i) {

        int u, v;

        scanf("%d%d", &u, &v);

        addEdge(u, v);

        addEdge(v, u);

    }

    vis[] = DFN;

    findSon();

    ++DFN;

    vis[] = DFN;

    LCM = calc();

//    cout << LCM << endl;

    ans = sum;

    sum /= LCM;

    sum *= LCM;

    LL be = , en = sum / LCM;

    while (be <= en) {

        LL mid = ((be + en) >> );

        ++DFN, flag = false;

        vis[] = DFN;

        dfs(, mid * LCM);

        if (flag) {

            en = mid - ;

        } else be = mid + ;

    }

    cout << ans - LCM * en << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

B. Apple Tree 暴力 + 数学

最新文章

热门文章