#1149082 (C++23) No.650 行列木クエリ

• 問題: No.650 行列木クエリ
• ユーザー: vjudge1
• 提出日時: 2026-02-22 20:05:12
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 994 bytes
• コンパイル時間: 1,913 ms
• コンパイル使用メモリ: 168,192 KB
• 実行使用メモリ: 15,164 KB
• 最終ジャッジ日時: 2026-02-22 20:05:19
• 合計ジャッジ時間: 6,843 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	-- * 1
other	WA * 2 TLE * 1 -- * 7

ソースコード

#include <iostream>
#include <vector>

const int N=214514,D=100;
int n,m,mod;
int a[N];
int tag[N][D],fa[N];
std::vector<int> e[N];

void dfs(int u,int f=0)
{
	fa[u]=f;
	for(int v:e[u])if(v!=f)dfs(v,u);
}

int main()
{
	scanf("%d %d",&n,&mod);
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n;i++)for(int j=0;j<=40;j++)tag[i][j]=1;
	scanf("%d",&m);
	int o,x,d,w;
	while(m--)
	{
		scanf("%d %d",&o,&x);
		if(o==1)
		{
			scanf("%d %d",&d,&w);
			while(d>=0&&x)
			{
				tag[x][d]=1ll*tag[x][d]*w%mod;
				if(d>=1)tag[x][d-1]=1ll*tag[x][d-1]*w%mod;
				if(x==1) // ??????????????????
				{
					for(int i=0;i<=d-2;i++)tag[1][i]=1ll*tag[1][i]*w%mod;
					break;
				}
				x=fa[x];
				d--;
			}
		}
		else
		{
			int ans=a[x];
			for(d=0;d<=40;d++) // ????? tag
			{
				if(!x)break;
				ans=1ll*ans*tag[x][d]%mod;
				x=fa[x];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}