链接:

https://codeforces.com/contest/1230/problem/E

题意:

Kamil likes streaming the competitive programming videos. His MeTube channel has recently reached 100 million subscribers. In order to celebrate this, he posted a video with an interesting problem he couldn't solve yet. Can you help him?

You're given a tree — a connected undirected graph consisting of n vertices connected by n−1 edges. The tree is rooted at vertex 1. A vertex u is called an ancestor of v if it lies on the shortest path between the root and v. In particular, a vertex is an ancestor of itself.

Each vertex v is assigned its beauty xv — a non-negative integer not larger than 1012. This allows us to define the beauty of a path. Let u be an ancestor of v. Then we define the beauty f(u,v) as the greatest common divisor of the beauties of all vertices on the shortest path between u and v. Formally, if u=t1,t2,t3,…,tk=v are the vertices on the shortest path between u and v, then f(u,v)=gcd(xt1,xt2,…,xtk). Here, gcd denotes the greatest common divisor of a set of numbers. In particular, f(u,u)=gcd(xu)=xu.

Your task is to find the sum

∑u is an ancestor of vf(u,v).

As the result might be too large, please output it modulo 109+7.

Note that for each y, gcd(0,y)=gcd(y,0)=y. In particular, gcd(0,0)=0.

思路:

暴力题..map记录每个点有多少个gcd的值, 从父节点继承下来.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

const int MOD = 1e9+7;

LL a[MAXN], ans = 0;

vector<int> G[MAXN];

unordered_map<LL, int> Mp[MAXN];

int n;

void Dfs(int u, int fa)

{

    for (auto it: Mp[fa])

    {

        LL gcd = __gcd(a[u], it.first);

        Mp[u][gcd] += it.second;

    }

    Mp[u][a[u]]++;

    for (auto it: Mp[u])

        ans = (ans + (it.first*it.second)%MOD)%MOD;

    for (auto x: G[u])

    {

        if (x == fa)

            continue;

        Dfs(x, u);

    }

}

int main()

{

    cin >> n;

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

        cin >> a[i];

    int u, v;

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

    {

        cin >> u >> v;

        G[u].push_back(v);

        G[v].push_back(u);

    }

    Dfs(1, 0);

    cout << ans << endl;

    return 0;

}

巴特西

Codeforces Round #588 (Div. 2) E. Kamil and Making a Stream(DFS)

链接:

题意:

思路:

代码:

最新文章

热门文章