题意：
给出n个点的树和长度为m的序列a。现需要给每条边染成r e d / b l u e色，要求按照a走的路径，经过的边数r − b = k，问方案数。
思路：
首先可以通过d f s 将序列a的路径经过每条边的次数c i统计出来。这样问题就变成了从c 1 , c 2 , … … c n − 1中选择一些数和为r，剩余的数和为b，满足r − b = k
假设s u m = c 1 + c 2 + … … + c n − 1 ,那么就可以得到r + b = s u m , r − b = k，解得r = s u m + k /2
问题变成了从c 1 , c 2 , … … c n − 1中选择一些数使得和为s u m + k/2
设d p [ i ] [ j ]表示从前i个数中选，和为j的方案数。将第一维去掉，第二层循环变成倒序，跟背包一样的。
上限的话，k = 1 e 5，假设a序列的相邻两个点为直径端点，每次都走1 e 3，一共走1 e 5,每条边都是100 次,和为1 e 5，这样( k + s u m ) / 2还是1 e 5，所以取1 e 5就够用啦。
代码：
// Problem: E - Red and Blue Tree // Contest: AtCoder - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） // URL: https://atcoder.jp/contests/abc222/tasks/abc222_e // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=998244353; int n,m,k,a[110],c[1100],dp[maxm]; vector<PII>g[1100]; int dfs(int u,int fa,int e){ if(e==u) return 1; for(auto t:g[u]){ int j=t.first,id=t.second; if(j==fa) continue; if(dfs(j,u,e)){ c[id]++;return 1; } } return 0; } int main(){ n=read,m=read,k=read; rep(i,1,m) a[i]=read; rep(i,1,n-1){ int u=read,v=read; g[u].push_back({v,i}); g[v].push_back({u,i}); } rep(i,1,m-1) dfs(a[i],-1,a[i+1]); int sum=0; rep(i,1,n-1) sum+=c[i]; if((sum+k)%2||(sum+k)<0){ puts("0");return 0; } dp[0]=1; for(int i=1;i<=n-1;i++) for(int j=1e5;j>=c[i];j--) dp[j]=(dp[j]+dp[j-c[i]])%mod; cout<<dp[(sum+k)/2]; return 0; }
