给出的是一个内向基环树森林，互相之间没有影响，只需考虑一棵内向基环树的情况。

设点 $i$ 的颜色为 $col_i\in \set{0,1}$，可以将边 $i$ 的贡献拆出来：

$$B_i D_{A_i}+B_i (C_{A_i}-D_{A_i})[col_i=col_{A_i}]$$

前者是定值，我们需要对每个点染色，最大化后者，后记 $w_i=B_i (C_{A_i}-D_{A_i})$。当然拆这个权也只是方便写式子，不拆也是一样的。

对于基环树，一个常用的方法是拆成树和环分别考虑，可以尝试使用。

树

不难想到可以做一个树形 dp：设 $f_{i,0/1}$ 为节点 $i$ 染上颜色 $0/1$ 后，其子树的最大值。

可以得到转移：

$$f_{u,0}=\sum_{v\in son_u} \max \set{f_{v,0}+w_v,f_{v,1}}$$$$f_{u,1}=\sum_{v\in son_u} \max \set{f_{v,1}+w_v,f_{v,0}}$$

用拓扑排序实现即可。

环

这个其实比较烦人，因为它是首尾相连的，直接 dp 会有后效性，可以直接固定环上一个点的颜色并把环拆成链进行计算，以将链首染色为 $0$ 为例：

设 $g_{i,0/1}$ 为考虑链上点 $i$ 以及 $i$ 之前的节点，在 $i$ 染色为 $0/1$ 的情况下的最大值。

进行递推：

对于链首 $u$ 的后继 $A_u$：

$$g_{A_u,0}=f_{u,0}+f_{A_u,0}+w_u$$ $$g_{A_u,1}=f_{u,0}+f_{A_u,1}$$

对于中间的节点 $i$：

$$g_{A_i,0}=f_{A_i,0}+\max \set{g_{i,0}+w_i,g_{i,1}}$$$$g_{A_i,1}=f_{A_i,1}+\max \set{g_{i,1}+w_i,g_{i,0}}$$

链尾 $v$ 便只有两种取值：$g_{v,0}+w_v$ 和 $g_{v,1}$，二者取一个最大值即可

对于染色为 $1$ 的情况，只有链首链尾部分需要修改，是类似的，这里略去。

基环树

将上述二者合起来即可。

时间复杂度 $O(n)$。

:::info[code]

namespace solve{
	int n,m,q,a[N],b[N],c[N],d[N],rd[N];
	ll w[N],f[N][2],g[N][2],ans;
	bitset<N> vis;
	void sol(){
		n=re();
		for(int i=1;i<=n;i++){
			a[i]=re(); b[i]=re();
			c[i]=re(); d[i]=re();
		}
		for(int i=1;i<=n;i++){
			w[i]=1ll*(c[a[i]]-d[a[i]])*b[i];
			ans+=1ll*d[a[i]]*b[i]; rd[a[i]]++;
		}
		queue<int> q;
		for(int i=1;i<=n;i++)
			if(rd[i]==0)q.push(i),vis[i]=1;
		while(!q.empty()){
			int u=q.front(); q.pop();
			f[a[u]][0]+=max(f[u][0]+w[u],f[u][1]);
			f[a[u]][1]+=max(f[u][1]+w[u],f[u][0]);
			if(--rd[a[u]]==0)q.push(a[u]),vis[a[u]]=1;
		}
		for(int i=1;i<=n;i++){
			if(vis[i])continue;
			ll res=-inf; vector<int> p;
			for(int u=i;!vis[u];u=a[u])vis[u]=1,p.pb(u);
			//case1
			g[a[i]][0]=f[a[i]][0]+f[i][0]+w[i];
			g[a[i]][1]=f[a[i]][1]+f[i][0];
			for(int j=1;j<p.size()-1;j++){
				int u=p[j];
				g[a[u]][0]=f[a[u]][0]+max(g[u][0]+w[u],g[u][1]);
				g[a[u]][1]=f[a[u]][1]+max(g[u][1]+w[u],g[u][0]);
			}
			int tmp=p[p.size()-1];
			res=max({res,g[tmp][0]+w[tmp],g[tmp][1]});
			//case2
			g[a[i]][0]=f[a[i]][0]+f[i][1];
			g[a[i]][1]=f[a[i]][1]+f[i][1]+w[i];
			for(int j=1;j<p.size()-1;j++){
				int u=p[j];
				g[a[u]][0]=f[a[u]][0]+max(g[u][0]+w[u],g[u][1]);
				g[a[u]][1]=f[a[u]][1]+max(g[u][1]+w[u],g[u][0]);
			}
			res=max({res,g[tmp][0],g[tmp][1]+w[tmp]});
			ans+=res;
		}
		cout<<ans<<'\n';
	}
}