题意：每个点都属于某个公司，公司对应一个权值，对于一条路径，如果一些点属于同一家公司，那么贡献只能算一次，给你一张图，路径只能从小的往大的走，现在问你从\(1\)到每个点的路径上的最大权值是多少。

题解：\(n\)最大为\(36\)，出现多个点的公司数最大为\(\frac{n}{2}\)，不难发现，对于一条路径，如果这条路径上的一些点仅有一家公司属于他们，这种情况是固定的，出现状态分裂的情况为出现多个点的那些公司，而这题的\(n\)很小，我们可以用二进制来压缩出现多个点的公司的状态。

设\(dp[i][j]\)表示，当前在\(i\)点，出现多个点的公司的选择情况为\(j\)，\(to\)表示上一个点，那么有：

1.\(i\)只有一家公司拥有他，那么我们直接从上一个点转移即可，\(dp[i][j]=max(dp[to][j]+w[c[i]])\).

2.\(i\)属于出现多个点的公司，那么先找到他在出现多个点的公司的新编号，那么根据当前的\(j\)直接转移就好

具体看代码吧，这里注意，有的人可能会说，假如我找到\(i\)的时候，\(j\)的状态表示了后面一些还没跑到的点会不会有问题，这里是没问题的，因为只有跑过的点会对状态有影响，没有遍历到的点选还是不选都一个样,因为值都是一样的

代码：

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 2e6 + 10;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m;
int c[N],w[N];
int dp[40][N];
vector<int> edge[N];
unordered_map<int,int> mp;
vector<int> v;
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&c[i]);
		mp[c[i]]++;
	}
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	for(auto w:mp){
		if(w.se>1) v.pb(w.fi);
	}
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d %d",&u,&v);
		edge[v].pb(u);
	}
	edge[1].pb(0);
	for(int i=1;i<=n;++i){
		int id=-1;
		for(int j=0;j<(int)v.size();++j){
			if(c[i]==v[j]){
				id=j;
				break;
			}
		}
		if(id==-1){
			for(int j=0;j<(1<<(int)v.size());++j){
				for(auto to:edge[i]){
					dp[i][j]=max(dp[i][j],dp[to][j]+w[c[i]]);
				}
			}
		}
		else{
			for(int j=0;j<(1<<(int)v.size());++j){
				if(j&(1<<id)){
					for(auto to:edge[i]){
						dp[i][j]=max(dp[i][j],dp[to][j^(1<<id)]+w[c[i]]);
					}
				}
				else{
					for(auto to:edge[i]){
						dp[i][j]=max(dp[i][j],dp[to][j]);
					}
				}
			}
		}
		int ans=0;
		for(int j=0;j<(1<<(int)v.size());++j) ans=max(ans,dp[i][j]);