P9437 『XYGOI round1』一棵树

记录

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5, M = 2 * N, mod = 998244353;
int n, idx;
int w[N], bit[N];
int h[N], to[M], ne[M];
bool st[N];
#define int long long
int base[10 * N];
int sum1, sum2, num1, num2, ans;

struct uni{
	int fro, tail, len;
} q[N];

inline void add(int u, int v){
	to[idx] = v, ne[idx] = h[u];
	h[u] = idx++;
	return;
}

inline int get_size(int now, int fa){
	if( st[now] )	return 0;
	int siz = 1;
	for(int i = h[now]; ~i; i = ne[i]){
		int j = to[i];
		if( j == fa )	continue;
		siz += get_size(j, now);
	}
	return siz;
}

inline int get_wc(int now, int fa, int all, int &wc){
	if( st[now] )	return 0;
	int mx = 0, siz = 1;
	for(int i = h[now]; ~i; i = ne[i]){
		int j = to[i];
		if( j == fa )	continue;
		int d = get_wc(j, now, all, wc);
		siz += d;
		mx = max(mx, d);
	}
	mx = max(mx, all - siz);
	if( mx <= all / 2 )   wc = now;
	return siz;
}

inline void get_dis(int now, int fa, int fro, int tail, int len, int& qt){
	if( st[now] )	return;
	ans = (ans + fro * num1 + sum1 * base[len] + tail * num2 + sum2) % mod;
	q[++qt] = {fro, tail, len};
	for(int i = h[now]; ~i; i = ne[i]){
		int j = to[i];
		if( j == fa )	continue;
		get_dis(j, now, (fro * base[bit[j]] + w[j]) % mod, (w[j] * base[len] + tail) % mod, len + bit[j], qt);
	}
	return;
}

inline void solve(int now){
	if( st[now] )	return;
	
	get_wc(now, -1, get_size(now, -1), now);
	st[now] = 1;
	
	sum1 = sum2 = num1 = num2 = 0;
	ans = (ans + w[now]) % mod;
	for(int i = h[now]; ~i; i = ne[i]){
		int j = to[i], qt = 0;
		get_dis(j, -1, w[j], w[j], bit[j], qt);
		for(int k = 1; k <= qt; k++){
			ans = (ans + q[k].tail * base[bit[now]] + w[now] + w[now] * base[q[k].len] + q[k].fro) % mod;
			sum1 = (sum1 + q[k].tail * base[bit[now]] + w[now]) % mod;
			num1++;
			sum2 = (sum2 + q[k].fro + w[now] * base[q[k].len]) % mod;
			num2 = (num2 + base[q[k].len + bit[now]]) % mod;
		}
	}
	
	for(int i = h[now]; ~i; i = ne[i])
		solve(to[i]);
	return;
}

signed main(){
	ios::sync_with_stdio(0);
    cin.tie(0);	cout.tie(0);
    
    cin >> n;
    base[0] = 1;
    for(int i = 1; i <= 10 * n; i++)
    	base[i] = base[i - 1] * 10 % mod;
	memset(h, -1, sizeof(h));
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		int k = w[i];
		if( !k )	bit[i] = 1;
		while( k ){
			bit[i]++;
			k /= 10;
		}
	}
	for(int i = 1; i < n; i++){
		int x;
		cin >> x;
		add(i + 1, x);
		add(x, i + 1);
	}
	solve(1);
	cout << ans;
	return 0;
}

1e6真不明白为什么淀粉质能T飞，希望有大佬能伸出援手帮忙卡常，或者证明这种方法就是卡不过去，不写换根dp是因为一直挂，所以就写点分治了