B·不会清数组·H

首先我们求出原树的 $SG$ 函数，这个东西很容易：$SG(\text{leaves})=0,SG(x)\text{ or\_eq }SG(y\in\text{son}(x))\text{ xor }1$。

然后考虑枚举附加边的起点 $u$。我们可以发现一个结论：我们不会去连返祖边。

简单证明一下（只考虑 Alice 先手，后手同理），当 $SG(u)=1$ 也就是在 $u$ 我们是先手必胜，那么显然我们不会去连边；当 $SG(u)=0$，此时先手必败，如果你连一个偶环没有意义，连一个奇环的话 Alice 跑完成必胜则 Bob 也可以跑一次从必败变成必胜，会形成无意义的无限循环，证毕。

那么我们的终点就是树上除了 $u$ 到根的路径上的所有满足 $SG$ 函数值为 $0$ 的点中的一个，我们当然贪心选择点权最小的。

那么此时有两种实现方法，一种是 $1~\log$ 的权值线段树，还有就是维护最小和次小，复杂度线性。

$\mathcal{O}(n\log_{2}n)$ （60 points）：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> pri;
LL T,n,t,A,B,poi[200010],head[200010],nxt[400010],to[400010],cntot,sg[200010],mx,expoi[200010],mp[200010];
void dfs(LL x){sg[x]=0; for(LL i=head[x];i;i=nxt[i])	dfs(to[i]),sg[x]|=(!sg[to[i]]);}
LL nodes[800010];
void ins(LL l,LL r,LL x,LL pos,LL val)
{
	if(l^r)
	{
		LL mid=(l+r)>>1;
		if(mid>=pos)	ins(l,mid,x<<1,pos,val);
		else	ins(mid+1,r,x<<1|1,pos,val);
		nodes[x]=nodes[x<<1]+nodes[x<<1|1];
	}
	else	nodes[x]+=val;
}
LL find(LL l,LL r,LL x)
{
	if(l^r)
	{
		LL mid=(l+r)>>1;
		if(nodes[x<<1])	return find(l,mid,x<<1);
		else	return find(mid+1,r,x<<1|1);
	}
	else	return mp[l];
}
LL getans(LL x,LL ty)
{
	if(!ty)
	{
		if(!sg[x])
		{
			ins(1,mx,1,expoi[x],-1);
			LL s=find(1,mx,1);
			if(!nodes[1])	s=-1;
			if(s==-1)	return ins(1,mx,1,expoi[x],1),-1; 
			LL res=A*poi[x]+B*s,tmp=0;
			for(LL i=head[x];i;i=nxt[i]) res=min(res,(tmp=getans(to[i],ty^1))==-1?LL(1e18):tmp);
			ins(1,mx,1,expoi[x],1);
			return res;
		}
		else	return 0;
	}
	else
	{
		LL num=0;
		for(LL i=head[x];i;i=nxt[i])	if(!sg[to[i]])	++num;
		if(num>1)	return -1;
		LL tmp=1e18;
		for(LL i=head[x];i;i=nxt[i]) if(!sg[to[i]])	tmp=min(tmp,getans(to[i],ty^1));
		return tmp;
	}
}
int main()
{
	scanf("%lld",&T); while(T--)
	{
		scanf("%lld %lld %lld %lld",&n,&t,&A,&B);
		for(LL i=2,f;i<=n;++i)
		{
			scanf("%lld",&f);
			nxt[++cntot]=head[f];
			to[cntot]=i;
			head[f]=cntot;
		}
		for(LL i=1;i<=n;++i)	scanf("%lld",&poi[i]),mx=max(mx,poi[i]),pri.push_back(poi[i]);
		sort(pri.begin(),pri.end()),pri.erase(unique(pri.begin(),pri.end()),pri.end());
		mx=pri.size();
		for(LL i=1;i<=n;++i)	mp[expoi[i]=lower_bound(pri.begin(),pri.end(),poi[i])-pri.begin()+1]=poi[i];
		dfs(1);
		if(sg[1]^t)	puts("0");
		else
		{
			for(LL i=1;i<=n;++i)	if(!sg[i]) ins(1,mx,1,expoi[i],1);
			printf("%lld\n",getans(1,t));
		}
		cntot=0,pri.clear();
		for(LL i=1;i<=n;++i)	head[i]=poi[i]=expoi[i]=0;
		for(LL i=1;i<=(n<<2);++i)	nodes[i]=0;
	}
	return 0;
}

$\mathcal{O}(n)$ （100 points）：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
LL T,n,t,A,B,poi[200010],head[200010],nxt[400010],to[400010],cntot,sg[200010],_fmin[200010],smin[200010];
void dfs(LL x)
{
	sg[x]=0,_fmin[x]=smin[x]=INF;
	for(LL i=head[x];i;i=nxt[i])
	{
		LL y=to[i];
		dfs(y),sg[x]|=(!sg[y]);
		if(_fmin[y]<_fmin[x])
		{
			smin[x]=min(_fmin[x],smin[y]);
			_fmin[x]=_fmin[y];
		}
	}
	if(!sg[x]&&poi[x]<_fmin[x])	smin[x]=_fmin[x],_fmin[x]=poi[x];
	else if(!sg[x]&&poi[x]<smin[x])	smin[x]=poi[x];
}
LL getans(LL x,LL ty,LL ho)
{
	if(!ty)
	{
		if(!sg[x])
		{
			LL tmp=ho,fmn=INF,smn=INF,pos=0;
			for(LL i=head[x];i;i=nxt[i])
			{
				LL y=to[i];
				tmp=min(tmp,_fmin[y]);
				if(_fmin[y]<fmn)	smn=fmn,fmn=_fmin[y],pos=y;
				else if(_fmin[y]<smn)	smn=_fmin[y];
			}
			if(tmp==INF)	return -1;
			LL res=A*poi[x]+B*tmp;
			for(LL i=head[x];i;i=nxt[i])
			{
				LL y=to[i];
				LL extmp=0;
				if(pos^y)	extmp=getans(y,ty^1,min(ho,fmn));
				else	extmp=getans(y,ty^1,min(ho,smn));
				if(~extmp)	res=min(res,extmp);
			}
			return res;
		}
		else	return 0;
	}
	else
	{
		LL num=0;
		for(LL i=head[x];i;i=nxt[i])	if(!sg[to[i]])	++num;	else ho=min(ho,_fmin[to[i]]);
		if(num>1)	return -1;
		for(LL i=head[x];i;i=nxt[i]) if(!sg[to[i]])	return getans(to[i],ty^1,ho);
	}
}
int main()
{
	scanf("%lld",&T); while(T--)
	{
		scanf("%lld %lld %lld %lld",&n,&t,&A,&B);
		for(LL i=2,f;i<=n;++i)
		{
			scanf("%lld",&f);
			nxt[++cntot]=head[f];
			to[cntot]=i;
			head[f]=cntot;
		}
		for(LL i=1;i<=n;++i)	scanf("%lld",&poi[i]);
		_fmin[0]=INF,dfs(1);
		if(sg[1]^t)	puts("0");
		else	printf("%lld\n",getans(1,t,INF));
		cntot=0;
		for(LL i=1;i<=n;++i)	head[i]=poi[i]=0;
	}
	return 0;
}