The Preliminary Contest for ICPC Asia Shenyang 2019 D. Fish eating fruit

Description:

State Z is a underwater kingdom of the Atlantic Ocean. This country is amazing. There are $n$ cities in the country and $n-1$ undirected underwater roads which connect all cities.

In order to save energy and avoid traffic congestion, the king promulgated a series of traffic regulations:

  1. Residents have to travel on fish!
  2. Residents need to feed the fish before you start your trip!The amount of food you feed the fish should be exactly the total distance of your journey.
  3. What kind of food to feed depends on the total distance of your journey!Total distance is a multiple of three. You should feed the fish with Durian. Total distance modulus $3$ equaling $1$ . It should be Papaya.Total distance modulus $3$ equaling $2$ . It should be Avocado!!!

Sure, fish like to eat these fruits very much.

Today is the first day of the king's decree. Because the residents here are not good at mathematics, they don't know how much fruit they need to give fish to go to other cities. So the king give an order to the energy minister Ynaonlctrm From all cities to all cities directly, which means that he will make $n*(n-1)$ trips.

For example, A - (5 mile) - B - (5 mile) - C, he needs to run the fish, starting at A, passing B, finally arriving C (papaya 10 kg), also he needs to start at C and end at A (papaya 10 kg). Indirect passage is useless. "I've passed City B, my dear emperor." "Oh! It's no use! Not directly! People in cities will never know how much the fish need to eat! The fish will surely die!!! You also need to take several trips which start at B or end with B!" The Emperor said.

It's really a tough task. Can you help him figure out how much fruit he needs to prepare for the emperor's mission?

Input:

Multiple input!

Fist line is $N$ . next $N-1$ line has three integer $a$ , $b$ and $c$ . It represent city $a$ and city $b$ is connected by a road of $c$ nautical miles. ( $1<n \le 10^4$ , $0 \le a,b<n$ , $1 \le c<10^5$ , $\sum{n} \le 10^5$ )

Output:

For each data, output three number, the amount of Durian, Papaya and Avocado he need. (the result could be very large, please output the result mod $10^9+7$ )

Sample Input:

5
0 1 2
0 2 3
0 3 7
0 4 6

Sample Output:

54 60 30

Sample Input:

8
4 7 1
7 5 1
4 6 1
6 3 1
5 2 1
2 1 1
7 0 1

Sample Output:

48 54 48

题目链接

分别求树上任意两点间距离 $\mod 3=0,1,2$ 的距离之和

题目与 [洛谷 P2634 [国家集训队]聪聪可可](https://www.luogu.org/problem/P2634) 十分相似,那么我们对于这道题来说只需要在对树进行点分治的时候统计所有 $\mod 3=0,1,2$ 的三类边,最后计算结果时暴力求和(太暴力会 $TLE$ )即可

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e4 + 5;
const int mod = 1e9 + 7;
int n;
struct Edge { int v; long long c; };
std::vector<Edge> g[maxn];
int sum, rt;
int son[maxn], sz[maxn];
bool vis[maxn];
void FindRoot(int u, int p) {
    sz[u] = 1; son[u] = 0;
    for (auto &e : g[u]) {
        int v = e.v;
        if (v == p || vis[v]) continue;
        FindRoot(v, u);
        sz[u] += sz[v];
        son[u] = std::max(son[u], sz[v]);
    }
    son[u] = std::max(son[u], sum - son[u]);
    if (son[u] < son[rt]) rt = u;
}
long long ans[3];
long long dis[maxn];
std::vector<long long> edge[3];
void GetCnt(int u, int p) {
    edge[dis[u] % 3].emplace_back(dis[u]);
    for (auto &e : g[u]) {
        int v = e.v;
        long long c = e.c;
        if (v == p || vis[v]) continue;
        dis[v] = dis[u] + c;
        GetCnt(v, u);
    }
}
void Cal(int u, long long c, bool f) {
    dis[u] = c;
    for (int i = 0; i < 3; ++i) edge[i].clear();
    GetCnt(u, 0);
    long long sz0 = edge[0].size(), sz1 = edge[1].size(), sz2 = edge[2].size();
    if (f) {
        for (auto &i : edge[0]) {
            ans[0] = (ans[0] + i * sz0 % mod) % mod;
            ans[1] = (ans[1] + i * sz1 % mod) % mod;
            ans[2] = (ans[2] + i * sz2 % mod) % mod;
        }
        for (auto &i : edge[1]) {
            ans[0] = (ans[0] + i * sz2 % mod) % mod;
            ans[1] = (ans[1] + i * sz0 % mod) % mod;
            ans[2] = (ans[2] + i * sz1 % mod) % mod;
        }
        for (auto &i : edge[2]) {
            ans[0] = (ans[0] + i * sz1 % mod) % mod;
            ans[1] = (ans[1] + i * sz2 % mod) % mod;
            ans[2] = (ans[2] + i * sz0 % mod) % mod;
        }
    }
    else {
        for (auto &i : edge[0]) {
            ans[0] = (ans[0] - i * sz0 % mod + mod) % mod;
            ans[1] = (ans[1] - i * sz1 % mod + mod) % mod;
            ans[2] = (ans[2] - i * sz2 % mod + mod) % mod;
        }
        for (auto &i : edge[1]) {
            ans[0] = (ans[0] - i * sz2 % mod + mod) % mod;
            ans[1] = (ans[1] - i * sz0 % mod + mod) % mod;
            ans[2] = (ans[2] - i * sz1 % mod + mod) % mod;
        }
        for (auto &i : edge[2]) {
            ans[0] = (ans[0] - i * sz1 % mod + mod) % mod;
            ans[1] = (ans[1] - i * sz2 % mod + mod) % mod;
            ans[2] = (ans[2] - i * sz0 % mod + mod) % mod;
        }
    }
}
void Dfs(int u) {
    Cal(u, 0, true);
    vis[u] = true;
    for (auto &e : g[u]) {
        int v = e.v;
        long long c = e.c;
        if (vis[v]) continue;
        Cal(v, c, false);
        rt = 0;
        sum = sz[v];
        son[rt] = n;
        FindRoot(v, u);
        Dfs(rt);
    }
}
int main() {
    while (~scanf("%d", &n)) {
        memset(ans, 0, sizeof(ans));
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1, u, v, c; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &c);
            ++u; ++v;
            g[u].push_back((Edge){v, c});
            g[v].push_back((Edge){u, c});
        }
        rt = 0;
        sum = son[rt] = n;
        memset(vis, false, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        memset(ans, 0, sizeof(ans));
        FindRoot(1, 0);
        Dfs(1);
        for (int i = 0; i < 3; ++i) ans[i] = (ans[i] * 2) % mod;
        printf("%lld %lld %lld\n", ans[0], ans[1], ans[2]);
    }
    return 0;
}
Last modification:September 18th, 2019 at 01:45 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment