提出 #52901323

---

ソースコード 拡げる

// LUOGU_RID: 157303998
#include <iostream>
#include <cstdio>
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
using namespace std;

const int mod = 998244353;

struct matr
{
	int ma[3][3];
} uni,mat[200010];

int n,q;
int a[200010],A[200010],res[200010];
int to[200010],nxt[200010],head[200010],cnt;
int dfn[200010],siz[200010],son[200010],dfncnt,tp[200010],la[200010],dep[200010],fa[200010];
struct node
{
	int xl,xr;
	matr M;
} tree[800010];
int cnt0[200010],g[200010];

int ksm(int x,int y)
{
	int res = 1;
	while (y)
	{
		if (y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

matr tms(matr x,matr y)
{
	matr re;
	for (int i = 1;i <= 2;i ++)
		for (int j = 1;j <= 2;j ++)
			re.ma[i][j] = 0;
	for (int i = 1;i <= 2;i ++)
		for (int j = 1;j <= 2;j ++)
			for (int k = 1;k <= 2;k ++)
				re.ma[i][j] = (re.ma[i][j] + x.ma[i][k] * y.ma[k][j] % mod) % mod;
	return re;
}

void pushup(int x)
{
	tree[x].M = tms(tree[rs].M,tree[ls].M);
}

void build(int x,int l,int r)
{
	tree[x].xl = l,tree[x].xr = r;
	if (l == r)
	{
		tree[x].M = mat[l];
		return ;
	}
	build(ls,l,mid),build(rs,mid + 1,r);
	pushup(x);
}

void upd(int x,int qx)
{
	int l = tree[x].xl,r = tree[x].xr;
	if (l == r)
	{
		tree[x].M = mat[l];
		return ;
	}
	if (qx <= mid) upd(ls,qx);
	else upd(rs,qx);
	pushup(x);
}

matr query(int x,int ql,int qr)
{
	int l = tree[x].xl,r = tree[x].xr;
	if (l >= ql && r <= qr) return tree[x].M;
	matr res = uni;
	if (mid < qr) res = query(rs,ql,qr);
	if (ql <= mid) res = tms(res,query(ls,ql,qr));
	return res;
}

void add(int x,int y)
{
	to[++ cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void dfs(int x)
{
	siz[x] = 1;
	for (int i = head[x];i;i = nxt[i])
	{
		int u = to[i];
		dep[u] = dep[x] + 1;
		fa[u] = x;
		dfs(u);
		siz[x] += siz[u];
		if (siz[u] > siz[son[x]]) son[x] = u;
	}
}

void dfss(int x,int topx)
{
	tp[x] = topx;
	dfn[x] = ++ dfncnt;
	if (!son[x])
	{
		la[topx] = x;
		mat[dfn[x]].ma[2][1] = a[x],mat[dfn[x]].ma[2][2] = 1;
		res[x] = a[x];
		return ;
	}
	g[x] = 1;
	dfss(son[x],topx);
	for (int i = head[x];i;i = nxt[i])
	{
		int u = to[i];
		if (u == son[x]) continue;
		dfss(u,u);
		g[x] = g[x] * (res[u] ? res[u] : 1) % mod;
		if (!res[u]) cnt0[x] ++;
	}
	A[x] = (cnt0[x] ? 0 : g[x]);
	mat[dfn[x]].ma[1][1] = A[x],mat[dfn[x]].ma[2][1] = a[x],mat[dfn[x]].ma[2][2] = 1;
	res[x] = (A[x] * res[son[x]] % mod + a[x]) % mod;
}

void upde(int x,int y,int k)
{
	mat[dfn[x]].ma[2][1] = (a[x] + k) % mod;
	while (tp[x] != tp[y])
	{
		if (dep[tp[x]] < dep[tp[y]]) swap(x,y);
		upd(1,dfn[x]);
		matr nw = query(1,dfn[tp[x]],dfn[la[tp[x]]]);
		cnt0[fa[tp[x]]] -= (res[tp[x]] == 0);
		g[fa[tp[x]]] = g[fa[tp[x]]] * ksm((res[tp[x]] ? res[tp[x]] : 1),mod - 2) % mod;
		cnt0[fa[tp[x]]] += (nw.ma[2][1] == 0);
		g[fa[tp[x]]] = g[fa[tp[x]]] * (nw.ma[2][1] ? nw.ma[2][1] : 1) % mod;
		if (!cnt0[fa[tp[x]]]) A[fa[tp[x]]] = g[fa[tp[x]]];
		else A[fa[tp[x]]] = 0;
		mat[dfn[fa[tp[x]]]].ma[1][1] = A[fa[tp[x]]];
		res[tp[x]] = nw.ma[2][1];
		x = fa[tp[x]];
	}
	if (dfn[x] > dfn[y]) swap(x,y);
	upd(1,dfn[y]);
}

signed main()
{
	A[0] = 1;
	scanf("%lld%lld",&n,&q);
	uni.ma[1][1] = uni.ma[2][2] = 1;
	for (int i = 2;i <= n;i ++)
	{
		int x;
		scanf("%lld",&x);
		add(x,i);
	}
	for (int i = 1;i <= n;i ++) scanf("%lld",a + i);
	dfs(1);
	dfss(1,1);
	build(1,1,n);
	while (q --)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		upde(x,1,(y - a[x] + mod) % mod);
		a[x] = y;
		printf("%lld\n",query(1,1,dfn[la[1]]).ma[2][1]);
	}
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:165:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  165 |         scanf("%lld%lld",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:170:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  170 |                 scanf("%lld",&x);
      |                 ~~~~~^~~~~~~~~~~
Main.cpp:173:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  173 |         for (int i = 1;i <= n;i ++) scanf("%lld",a + i);
      |                                     ~~~~~^~~~~~~~~~~~~~
Main.cpp:180:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  180 |                 scanf("%lld%lld",&x,&y);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~

ジャッジ結果