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
", a, b, c);
	}
	return 0;
}