记录

看到最优解O(n)算法140ms，我感觉应该是卡不过去了，所以有没有大佬能造一个数据把一下代码卡飞？

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5, M = 2 * N, mod = 998244353;

#define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
namespace FastIO { static constexpr int S = 1 << 21; char ibuf[S], obuf[S], *p1 = ibuf, *p2 = ibuf, *p3 = obuf; inline void pc(char c) { if(p3 - obuf == S) fwrite(obuf, 1, S, stdout), p3 = obuf; *p3++ = c; } inline void write(char c) { pc(c); } template<typename _Tp>inline void read(_Tp& x) { x = 0; char c = gc(); int f = 0; for(; !std::isdigit(c); c = gc()) f |= c == '-'; for(; std::isdigit(c); c = gc()) x = x * 10 + (c ^ 48); return f ? x = ~x + 1 : 1, void(); } template<typename _Tp>inline void write(_Tp x) { static int stk[40]; int tp = 0; if(!x) return pc('0'), void(); if(x < 0) pc('-'), x = ~x + 1; while(x) stk[++tp] = x % 10, x /= 10; while(tp) pc(stk[tp--] + '0'); } template<typename _Tp>inline void writesp(_Tp x) { write(x), pc(' '); } template<typename _Tp>inline void writeln(_Tp x) { write(x), pc('\n'); } template<typename _Tp, typename ...Args>inline void read(_Tp& x, Args& ...args) { read(x), read(args...); } template<typename _Tp, typename ...Args>inline void write(_Tp x, Args ...args) { write(x), write(args...); } template<typename _Tp, typename ...Args>inline void writesp(_Tp x, Args ...args) { writesp(x), writesp(args...); } template<typename _Tp, typename ...Args>inline void writeln(_Tp x, Args ...args) { writeln(x), writeln(args...); } inline void flush() { fwrite(obuf, p3 - obuf, 1, stdout); } }
using namespace FastIO;

#define i64 long long
int n, idx;
int w[N], bit[N];
int h[N], to[M], ne[M];
bool st[N];
i64 base[10 * N];
i64 sum1, sum2, num1, num2, ans;

struct uni{
	i64 fro, tail;
	int 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, i64 fro, i64 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(){
    read(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++){
		read(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;
		read(x);
		add(i + 1, x);
		add(x, i + 1);
	}
	solve(1);
	write(ans);
	flush();
	return 0;
}

复杂度肯定是nlogn，不明白为什么过不去1e6