2019 沈阳网络赛 Fish eating fruit

这题看了三个月，终于过了，第一次看的时候没学树形DP，想用点分治但是不会

后来学了二次扫描，就有点想法了。。。。

这东西也真就玄学了吧。。。

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn  = 1e5 + 7;

const ll mod = 1e9 + 7;

struct Node {

	int p;

	ll len;

	Node(int _p, ll _len) :p(_p), len(_len) {}

};

int n;

ll dp[maxn][5];

ll cnt[maxn][6];

vector<Node>G[maxn];

void insert(int be, int en, ll len) {

	G[be].push_back(Node(en, len));

}

int dfs2(int x, int fa) {

	for (int i = 0; i < G[x].size(); i++) {

		int p = G[x][i].p;

		ll len = G[x][i].len;

		if (p == fa) continue;

		dfs2(p, x);

		for (int a = 0; a < 3; a++) {

			dp[x][(a + len) % 3] += (dp[p][a] + cnt[p][a] * len) % mod;

			cnt[x][(a + len) % 3] += cnt[p][a];

			dp[x][(a + len) % 3] %= mod;

		}

		dp[x][len % 3] += len;

		dp[x][len % 3] %= mod;

		cnt[x][len % 3] ++;

	}

	return 0;

}

ll ans[10];

ll son[10];

int dfs(int x, int fa) {

	for (int i = 0; i < G[x].size(); i++) {

		int p = G[x][i].p;

		ll len = G[x][i].len;

		if (p == fa) continue;

		for (int a = 0; a < 3; a++) {

			ans[(a + len) % 3] = (dp[x][(a + len) % 3] - (cnt[p][a] * len + dp[p][a])) % mod;

			ans[(a + len) % 3] += mod;

			ans[(a + len) % 3] %= mod;

			son[(a + len) % 3] = cnt[x][(a + len) % 3] - cnt[p][a];

		}

		son[len % 3]--;

		ans[len % 3] = (ans[len % 3] - len + mod) % mod;

		//删除了多的边

		for (int a = 0; a < 3; a++) {

			dp[p][(a + len) % 3] += (ans[a] + son[a] * len) % mod;

			dp[p][(a + len) % 3] %= mod;

			cnt[p][(a + len) % 3] += son[a];

		}

		cnt[p][len % 3]++;

		dp[p][len % 3] += len;

		dp[p][len % 3] %= mod;

		dfs(p, x);

	}

	return 0;

}

int main() {

	while (~scanf("%d", &n)) {

		for (int i = 0; i <= n; i++) G[i].clear();

		memset(dp, 0, sizeof(dp));

		memset(cnt, 0, sizeof(cnt));

		int be, en;

		ll len;

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

			scanf("%d %d %lld", &be, &en, &len);

			insert(be, en, len);

			insert(en, be, len);

		}

		dfs2(0, -1);

		dfs(0, -1);

		ll a = 0, b = 0, c = 0;

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

			a = (a + dp[i][0]) % mod;

			b = (b + dp[i][1]) % mod;

			c = (c + dp[i][2]) % mod;

		}

		printf("%lld %lld %lld\n", a, b, c);

	}

	return 0;

}