【2021集训队出题】愚蠢的在线法官

by AmanoKumiko

Description

给出一颗\(n\)个点的树，再给出每个点的权值\(v\)

然后给出一个长度为\(k\)的数组\(A\)

然后对于\(k*k\)的矩阵，\(i,j∈[1,k]\)，\(V_{i,j}=v_{lca(A_i,A_j)}\)，求它的行列式

Input

第一行两个整数\(n,k\)

第二行\(n\)个数，表示权值

第三行\(k\)个数表示\(A\)

接下来\(n-1\)行，读入一颗树

Output

一行一个数表示答案对\(998244353\)取模的结果

Sample Input

Sample Output

Data Constraint

\(1\le n,k\le 5*10^5,v_i∈[0,998244353),A_i∈[1,n]\)

Solution

一些高代：

1.行列式交换两行不变

2.行列式中某一行提出一个公因子\(x\)，行列式乘上\(x\)

3.行列式中某一行中\(a_i\)都表示成\(b_i+c_i\)的形式，那么行列式等于取\(b_i\)和\(c_i\)情况下的和

4.行列式中两行相减，行列式不变

首先，如果\(A\)中存在相等的数，答案是\(0\)

然后我们考虑树形\(dp\)

设\(f_i\)表示以\(i\)为根的子树的行列式

考虑加入一个子树时的贡献

那么变成这种形式

\[\left| \begin{array}{} A & B\\ C & D \end{array} \right| \]

\(A\)是原答案，\(D\)是子树的答案

令\(x=v_u\)，那么\(B,C\)均为\(x\)

我们直接给一行减去\(x\)

然后变成了

\[x\left| \begin{array}{} 1&1&1&1\\ a'&a'&0&0\\ 0&0&a'&a'\\ 0&0&a'&a' \end{array} \right| \]

\[\left| \begin{array}{} a&a&x&x\\ a&a&x&x\\ x&x&a&a\\ 0&0&a'&a' \end{array} \right| \]

的形式

对于前者，我们引入一个\(g_i\)表示在\(i\)的行列式中，将某一行全部变成\(1\)的答案

对于后者，我们可以继续让别的行减去\(x\)，最后变为

\[\left| \begin{array}{} a'&a'&0&0\\ a'&a'&0&0\\ 0&0&a'&a'\\ 0&0&a'&a' \end{array} \right| \]

再令\(s=\prod_{v∈son(u)}f_v\)

那么有\(f_u=\sum_{v∈son(u)}\frac{g_vxs}{f_v}+s\)

而在这种情况下，

后代求的行列式实际上是后代所有\(v\)减去当前\(v\)的行列式，这个随便处理一下就可以了

对于\(g\)的递推，类似

然后再特判一下当前点在\(A\)中的情况就行了

Code

#include
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define Fs(i,a) for(int i=last[a];i;i=e[i].next)
#define LL long long
#define mo 998244353
#define N 500010

int n,k,a,b,A[N],vis[N],tot,last[N];
LL v[N],f[N],g[N],tag;

struct node{int en,next;}e[N*2];

void add(int x,int y){e[++tot]=(node){y,last[x]};last[x]=tot;}

LL mi(LL x,LL y){
	if(y==1)return x;
	return y%2?x*mi(x*x%mo,y/2)%mo:mi(x*x%mo,y/2);
}

void dfs(int now,int pre){
	v[now]=(v[now]-tag+mo)%mo;
	(tag+=v[now])%=mo;
	LL fs=1;int s=0;
	Fs(i,now)if(e[i].en!=pre)dfs(e[i].en,now),fs=fs*f[e[i].en]%mo,s++;
	if(vis[now]){
		if(!s)f[now]=v[now],g[now]=1;
		else f[now]=fs*v[now]%mo,g[now]=fs;
	}else{
		f[now]=fs;
		Fs(i,now)if(e[i].en!=pre){
			LL x=mi(f[e[i].en],mo-2);
			(f[now]+=fs*x%mo*g[e[i].en]%mo*v[now]%mo)%=mo;
			(g[now]+=fs*x%mo*g[e[i].en]%mo)%=mo;
		}
	}
	tag=(tag-v[now]+mo)%mo;
}

int main(){
	scanf("%d%d",&n,&k);
	F(i,1,n)scanf("%lld",&v[i]);
	F(i,1,k){
		scanf("%d",&A[i]);
		if(vis[A[i]]){printf("0");return 0;}
		vis[A[i]]=1;
	}
	F(i,1,n-1)scanf("%d%d",&a,&b),add(a,b),add(b,a);
	dfs(1,0);
	printf("%lld",f[1]);
	return 0;
}

题解线性代数 NOI

【2021集训队出题】愚蠢的在线法官