link
链式前向星，O(4n)（4e7<5e7，不知道为什么50分TLE）: （c[x]表点权，f[x]表父节点）

#include <stdio.h>
#define ll long long
#define MAX_N 10200202
typedef struct{
	int to,next;
} Edge;
typedef struct{
	Edge pool[MAX_N<<1];
	int tops[MAX_N],tot;
} Tree;
inline void build(Tree* map,int x,int y){
	map->pool[++map->tot]=(Edge){y,map->tops[x]};
	map->tops[x]=map->tot;
	map->pool[++map->tot]=(Edge){x,map->tops[y]};
	map->tops[y]=map->tot;
}
typedef unsigned int uint;
inline uint get_next(uint seed){
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}
uint c[MAX_N];
int f[MAX_N];
Tree map;
long long j,ans;
int n;
uint seed;
void dfs(ll x,ll minthen){
	if(c[x]<minthen)
	{
		minthen=c[x];
		ans+=c[x];
	}
	else
		ans+=minthen;
	for(register Edge pzq=map.pool[map.tops[x]];pzq.to;pzq=map.pool[pzq.next])
		if(pzq.to!=f[x])
			dfs(pzq.to,minthen);
}
int main()
{
	scanf("%d %lld",&n,&j);
	seed=j;
	n++;
	for (register int i = 1; i < n; i++)
		c[i] = seed=get_next(seed);
	for (register int i = 2; i < n; i++)
		build(&map,i,f[i] = (seed=get_next(seed)) % (i - 1) + 1);
	n--;
	dfs(1,c[1]);
	printf("%lld",ans);
	return 0;
}