C++(g++ 7.5.0) 解法, 执行用时: 158ms, 内存消耗: 49264K, 提交时间: 2023-07-29 22:48:10

#include <bits/stdc++.h>
using i64=long long;
int n, m;
const int N = 1e5 + 10;
typedef std::pair<int, int> PII;
std::map<int, int> tr[N];
int h[N], ne[N << 1], e[N << 1], w[N << 1], idx, sz[N];
inline void add(int a, int b, int c) {
	ne[idx] = h[a], e[idx] = b, w[idx] = c, h[a] = idx ++;
}
inline void add(int a, int b) {
	ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}
int val[N << 5], root[N << 5], tot, l[N << 5], r[N << 5], nxt[N << 5];
int dfn[N], timedelta, id[N];

inline void insert(int &u, int L, int R, int x, int v) {
	int last = u;
	u = ++ tot;
	if (L == R) {
		val[u] = v;
		return ;	
	}
	l[u] = l[last];
	r[u] = r[last];
	int mid = L + R >> 1;
	if (x <= mid) insert(l[u], L, mid, x, v);
	else insert(r[u], mid + 1, R, x, v);
}
inline int query(int u, int L, int R, int x) {
	if (L == R) return val[u];
	
	int mid = L + R >> 1;
	if (x <= mid)	return query(l[u], L, mid, x);
	return query(r[u], mid + 1, R, x);
}
inline void solve() {
	std::cin >> n;	
	memset(h, -1, sizeof h);
	for (int i = 0; i < n; i ++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	{
		std::function<void(int, int)> dfs = [&](int u, int fa) -> void{
			sz[u] = 1;
			for (int i = h[u]; ~i; i = ne[i]) {
				int j = e[i], v = w[i];
				if (j == fa)	continue;
				tr[u][j] = v;
				dfs(j, u);
				sz[u] += sz[j];
			}
		};
		dfs(0, -1);
	}
	
	{
		int p = 0;
		std::queue<int> q;
		for (auto &[x, v]: tr[p]) {
			q.push(x);
			nxt[v] = 0;
			insert(root[p], 1, 1e5, v, x);
		}			
		while (!q.empty()) {
			int tq = q.front();
			q.pop();
			root[tq] = root[nxt[tq]];
			for(auto &[x, v]: tr[tq]){
				int t = query(root[tq], 1, 1e5, v);
				nxt[x] = t;
				insert(root[tq], 1, 1e5, v, x);	
				q.push(x);
			}
		}
	}
	memset(h, -1, sizeof h);
	idx = 0;
	
	{
		std::vector<long long> dp(n + 1);
		for (int i = 1; i <= n; i ++) {
			dp[nxt[i]] += sz[i];
			add(nxt[i], i);
		}
		
		std::function<void(int)> dfs = [&](int u) -> void{
			for (int i = h[u]; ~i; i = ne[i]) {
				int j = e[i];
				dfs(j);
				dp[u] += dp[j];
			}
		};
		dfs(0);
		
		for (int i = 1; i <= n; i ++) dp[i] += sz[i];
		for (int i = 1; i <= n; i ++)	std::cout << dp[i] << '\n';
	}
}
int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int _ = 1;
	while (_ --) solve();
	return 0;
}

C++ 解法, 执行用时: 496ms, 内存消耗: 284812K, 提交时间: 2021-06-08 19:09:00

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
const int N=1e5+10;

ll ans[N];
int fail[N],q[N],t;
vector<pair<int, int>>g[N];
rope<int>go[N];
int main() {
    int n;cin>>n;
    for(int i=0; i<n; i++) {
        int u,v,c; scanf("%d%d%d",&u,&v,&c);
        g[u].emplace_back(v, c);
    }
    go[0]=rope<int>(N, 0);
    q[t++]=0;
    for(int h=0;h<t; h++) {
        int u=q[h];
        go[u]=go[fail[u]];
        for(auto [v,c]:g[u]){
            fail[v]=go[u][c];
            go[u].replace(c,v);
            q[t++]=v;
        }
    }
    for(int i=t-1;i;i--) {
        int u=q[i];
        ans[u]=1;
        for(auto [v,c]:g[u]) {
            ans[u]+=ans[v];
        }
    }
    for(int i=t-1;i;i--){
        int u=q[i];
        ans[fail[u]]+=ans[u];
    }
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}