stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int A,B,C,X,Y;

int main() {

	cin>>A>>B>>C>>X>>Y;

	int sum=0;

	int minm=min(X,Y);

	if(2*C>A+B){

		sum+=minm*(A+B);

	}

	else

		sum+=minm*2*C;

	if(minm==X){

		int d=Y-X;

		if(C*2>B)

		sum+=d*B;

		else

		sum+=d*2*C;

	}

	else if(minm==Y){

		int d=X-Y;

		if(C*2>A)

		sum+=d*A;

		else

		sum+=d*2*C;

	}

	cout<<sum<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;



int a,b,c,x,y;



int main(){

//	freopen("inb.txt","r",stdin);

	scanf("%d%d%d%d%d", &a, &b, &c, &x, &y);

	int com = min(x,y);//a b棋盘公共的部分 com套a+b 

	int sum = 0; 

	if(a+b>=c*2){//套装更优惠 

		sum += com*c*2; 

		if(x>=y){

			if(a>=c*2){

				sum += (x-y)*2*c;

			}else{

				sum += (x-y)*a;

			}	

		}else{

			if(b>=c*2){

				sum += (y-x)*2*c;

			}else{

				sum += (y-x)*b;

			}

		}

	}else{//单买更优惠 

		sum = x*a + y*b; 

	}

	printf("%d\n", sum);

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//ツ暗。ツつ、ツづァツつオツつ「

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <utility>

using namespace std;

struct road{

	int a,b,l;

	road(int a_,int b_,int l_):a(a_),b(b_),l(l_){}

};

typedef pair<int,int> pii;

int main(){

	int n,m,k,a,b,l,s;

	vector<road> rd;

	vector<pii> town[3001];

	int len[3001];

	priority_queue<pii,vector<pii>,greater<pii> > qu;

	int inf = 1e9;



	for(cin>>n>>m>>k;m--;rd.push_back(road(a,b,l))){

		cin>>a>>b>>l;

		town[a].push_back(make_pair(b,l));

		town[b].push_back(make_pair(a,l));

	}

	for(;k--;qu.push(make_pair(0,s)))

		cin>>s;



	for(fill(len,len+n+1,-1);!qu.empty();){

		pii pi = qu.top();

		qu.pop();

		if( len[pi.second] == -1 ){

			len[pi.second] = pi.first;

			for(

				vector<pii>::iterator it=town[pi.second].begin();

				it != town[pi.second].end();

				++it

			){

				qu.push(make_pair(pi.first+it->second,it->first));

			}

		}

	}

	

	s=0;

	for(vector<road>::iterator it = rd.begin(); it != rd.end();	++it ){

		s = max(max( s, len[a] ),

				max( len[b], (len[it->b] + it->l - len[it->a] + 1)/2 + len[it->a] )

		);

	}

	cout << s << endl;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>

#include <functional>

using namespace std;



typedef pair<int,int> pii;



int main(){

	int n, m, k, u;

	scanf("%d%d%d", &n, &m, &k);



	vector<int> a(m), b(m), L(m);

	vector<vector<pii> > G(n + 1);

	for(int i = 0; i < m; ++i){

		scanf("%d%d%d", &a[i], &b[i], &L[i]);

		G[a[i]].push_back(pii(L[i], b[i]));

		G[b[i]].push_back(pii(L[i], a[i]));

	}



	priority_queue<pii,vector<pii>,greater<pii> > pq;

	vector<int> d(n + 1, 500000000);

	for(int i = 0; i < k; ++i){

		scanf("%d", &u);

		d[u] = 0;

		pq.push(pii(0, u));

	}



	while(!pq.empty()){

		int e = pq.top().first;

		u = pq.top().second;

		pq.pop();

		if(d[u] != e){ continue; }

		for(size_t i = 0; i < G[u].size(); ++i){

			int v = G[u][i].second;

			int f = e + G[u][i].first;

			if(d[v] > f){

				d[v] = f;

				pq.push(pii(f, v));

			}

		}

	}



	int ans = 0;

	for(int i = 0; i < m; ++i){

		int e = d[a[i]];

		int f = d[b[i]];

		int r = max(max(e, f), e + (f - e + L[i] + 1) / 2);

		ans = max(ans, r);

	}

	printf("%d\n", ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <utility>

using namespace std;struct road{int a,b,l;road(int a_,int b_,int l_):a(a_),b(b_),l(l_){}};typedef pair<int,int> pii;int main(){int n,m,k,a,b,l,s;vector<road> rd;vector<pii> town[3001];int len[3001];priority_queue<pii,vector<pii>,greater<pii> > qu;for(cin>>n>>m>>k;m--;rd.push_back(road(a,b,l))){cin>>a>>b>>l;town[a].push_back(make_pair(b,l));town[b].push_back(make_pair(a,l));}for(;k--;qu.push(make_pair(0,s)))cin>>s;for(fill(len,len+n+1,-1);!qu.empty();){pii pi = qu.top();qu.pop();if( len[pi.second] == -1 ){len[pi.second] = pi.first;for(vector<pii>::iterator it=town[pi.second].begin();it != town[pi.second].end();++it){qu.push(make_pair(pi.first+it->second,it->first));}}}s=0;for(vector<road>::iterator it = rd.begin(); it != rd.end();++it ){s = max(max( s, len[a] ),max( len[b], (len[it->b] + it->l - len[it->a] + 1)/2 + len[it->a] ));}cout << s << endl;}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>

#include <functional>

using namespace std;



typedef pair<int,int> pii;



int main(){

	int n, m, k, u;

	scanf("%d%d%d", &n, &m, &k);



	vector<int> a(m), b(m), L(m);

	vector<vector<pii> > G(n + 1);

	for(int i = 0; i < m; ++i){

		scanf("%d%d%d", &a[i], &b[i], &L[i]);

		G[a[i]].push_back(pii(L[i], b[i]));

		G[b[i]].push_back(pii(L[i], a[i]));

	}



	priority_queue<pii,vector<pii>,greater<pii> > pq;

	vector<int> d(n + 1, 500000000);

	for(int i = 0; i < k; ++i){

		scanf("%d", &u);

		d[u] = 0;

		pq.push(pii(0, u));

	}



	while(!pq.empty()){

		int e = pq.top().first;

		u = pq.top().second;

		pq.pop();

		if(d[u] != e){ continue; }

		for(size_t i = 0; i < G[u].size(); ++i){

			int v = G[u][i].second;

			int f = e + G[u][i].first;

			if(d[v] > f){

				d[v] = f;

				pq.push(pii(f, v));

			}

		}

	}



	int ans = 0;

	for(int i = 0; i < m; ++i){

		int e = d[a[i]];

		int f = d[b[i]];

		int r = max(max(e, f), e + (f - e + L[i] + 1) / 2);

		ans = max(ans, r);

	}

	printf("%d\n", ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<utility>

using namespace std;struct road{int a,b,l;road(int a_,int b_,int l_):a(a_),b(b_),l(l_){}};typedef pair<int,int> pii;int main(){int n,m,k,a,b,l,s;vector<road>rd;vector<pii>town[3001];int len[3001];priority_queue<pii,vector<pii>,greater<pii> >qu;for(cin>>n>>m>>k;m--;rd.push_back(road(a,b,l))){cin>>a>>b>>l;town[a].push_back(make_pair(b,l));town[b].push_back(make_pair(a,l));}for(;k--;qu.push(make_pair(0,s)))cin>>s;for(fill(len,len+n+1,-1);!qu.empty();){pii pi=qu.top();qu.pop();if(len[pi.second]==-1){len[pi.second]=pi.first;for(vector<pii>::iterator it=town[pi.second].begin();it!=town[pi.second].end();++it)qu.push(make_pair(pi.first+it->second,it->first));}}s=0;for(vector<road>::iterator it=rd.begin();it!=rd.end();++it){s=max(max(s,len[a]),max(len[b],(len[it->b]+it->l-len[it->a]+1)/2+len[it->a]));}cout<<s<<endl;}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>

#include <functional>

using namespace std;



typedef pair<int,int> pii;



int main(){

	int n, m, k, u;

	scanf("%d%d%d", &n, &m, &k);



	vector<int> a(m), b(m), L(m);

	vector<vector<pii> > G(n + 1);

	for(int i = 0; i < m; ++i){

		scanf("%d%d%d", &a[i], &b[i], &L[i]);

		G[a[i]].push_back(pii(L[i], b[i]));

		G[b[i]].push_back(pii(L[i], a[i]));

	}



	priority_queue<pii,vector<pii>,greater<pii> > pq;

	vector<int> d(n + 1, 500000000);

	for(int i = 0; i < k; ++i){

		scanf("%d", &u);

		d[u] = 0;

		pq.push(pii(0, u));

	}



	while(!pq.empty()){

		int e = pq.top().first;

		u = pq.top().second;

		pq.pop();

		if(d[u] != e){ continue; }

		for(size_t i = 0; i < G[u].size(); ++i){

			int v = G[u][i].second;

			int f = e + G[u][i].first;

			if(d[v] > f){

				d[v] = f;

				pq.push(pii(f, v));

			}

		}

	}



	int ans = 0;

	for(int i = 0; i < m; ++i){

		int e = d[a[i]];

		int f = d[b[i]];

		int r = max(max(e, f), e + (f - e + L[i] + 1) / 2);

		ans = max(ans, r);

	}

	printf("%d\n", ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<queue>

#include<map>

#include<cstdio>

#include<cmath>

#define INF 500000000

using namespace std;



typedef pair<int,int> P;



int n,m,k;

int l[100100],a[100100],b[100100];

vector<P> g[5000];

int d[5000],w[5000];

int s[5000];



int main(){

  cin >> n >> m >> k;

  for(int i=0;i<m;i++){

    cin >> a[i] >> b[i] >> l[i];

    a[i]--; b[i]--;

    g[a[i]].push_back(P(l[i],b[i]));

    g[b[i]].push_back(P(l[i],a[i]));

  }

 

  for(int i=0;i<k;i++){cin >> s[i]; s[i]--;}



  for(int i=0;i<n;i++)d[i] = INF;

  priority_queue<P,vector<P>,greater<P> > q;

  for(int i=0;i<k;i++){

    d[s[i]] = 0;

    q.push(P(0,s[i]));

  }



  while(q.size()){

    P p = q.top(); q.pop();

    int cost = p.first, pos = p.second;

    

    for(int i=0;i<(int)g[pos].size();i++){

      int dis = cost + g[pos][i].first;

      int next = g[pos][i].second;

      

      if(dis<d[next]){

	d[next] = dis;

	q.push(P(dis,next));

      }

    }

  }



  double ans = 0.0;

  for(int i=0;i<m;i++){

    if(fabs(d[a[i]] - d[b[i]]) >= l[i]){

      ans = max(ans,(double)max(d[a[i]],d[b[i]]));

    }else{

      ans = max(ans,(double)(l[i]+d[a[i]]+d[b[i]])/2);

    }

  }

  cout << (int)(ans+1e-9+0.5) << endl;

}

  

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

typedef pair<int,int> edge;



const int INF = 1e9;



int main(){

  int n,m,k;

  scanf("%d%d%d",&n,&m,&k);

  

  vector< vector<edge> > g(n);

  rep(i,m){

    int a,b,l;

    cin >> a >> b >> l; a--; b--;

    g[a].push_back(edge(l,b));

    g[b].push_back(edge(l,a));

  }



  vector<int> d(n,INF);

  priority_queue< edge, vector<edge>, greater<edge> > q;

  rep(i,k){

    int s; cin >> s; s--;

    d[s] = 0;

    q.push(edge(0,s));

  }



  while(q.size()){

    edge x = q.top(); q.pop();

    int c = x.first, v = x.second;

    

    for(edge e : g[v]){

      int nc = c + e.first;

      int u = e.second;

      

      if(d[u] > nc){

	d[u] = nc;

	q.push( edge(nc, u) );

      }

    }

  }

  

  int ans = 0;

  rep(a,n){

    for(edge e : g[a]){

      int l = e.first, b = e.second;

      

      int A = min(d[a], d[b]), B = max(d[a], d[b]);

      if(A+l < B){

	ans = max(ans, A+l);

      }else{

	ans = max(ans, (A+B+l+1)/2);

      }

    }

  }

  cout << ans << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <vector>

using namespace std;

const int N = 5010, mod = 1e9 + 7;

int n, x, y, dp[N][N], siz[N], tmp[N], g[N];

vector<int> G[N];

void dfs(int u, int fa) {

    siz[u] = 1; 

    dp[u][1] = 1;

    for(auto v : G[u]) {

        if(v == fa) continue;

        dfs(v, u);

        for(int i = 1; i <= siz[u] + siz[v]; ++i) tmp[i] = 0;

        for(int i = 1; i <= siz[u]; ++i)

            for(int j = 0; j <= siz[v]; ++j)

                (tmp[i + j] += 1ll * dp[u][i] * dp[v][j] % mod) %= mod;

        siz[u] += siz[v];

        for(int i = 1; i <= siz[u]; ++i) dp[u][i] = tmp[i];

    }

    for(int i = 2; i <= siz[u]; i += 2)

        (dp[u][0] += 1ll * dp[u][i] * g[i] % mod) %= mod;

    if(fa) dp[u][0] = mod - dp[u][0];

}

int main() {

    scanf("%d", &n);

    for(int i = 1; i < n; ++i) {

        scanf("%d %d", &x, &y);

        G[x].push_back(y); 

        G[y].push_back(x);

    }

    g[0] = 1;

    for(int i = 2; i <= n; i += 2)

        g[i] = 1ll * g[i - 2] * (i - 1) % mod;

    dfs(1, 0);

    printf("%d\n", dp[1][0]);

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <algorithm>

using namespace std;



const int MAXN = 5000;

const int MOD = int(1E9) + 7;

const int INV2 = (MOD + 1) >> 1;



struct edge{

	edge *nxt; int to;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = edges;

void addedge(int u, int v) {

	edge *p = (++ecnt);

	p->to = v, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->nxt = adj[v], adj[v] = p;

}



int fct[MAXN + 5], ifct[MAXN + 5], coef[MAXN + 5];

void init() {

	fct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		fct[i] = 1LL*fct[i-1]*i%MOD;

	ifct[1] = 1;

	for(int i=2;i<=MAXN;i++)

		ifct[i] = (MOD - 1LL*(MOD/i)*ifct[MOD%i]%MOD);

	ifct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		ifct[i] = 1LL*ifct[i-1]*ifct[i]%MOD;

	int t = INV2;

	for(int i=2;i<=MAXN;i+=2,t=1LL*t*INV2%MOD)

		coef[i] = 1LL*fct[i]*ifct[i/2]%MOD*t%MOD;

}



int dp[MAXN + 5][MAXN + 5], siz[MAXN + 5];

void dfs(int x, int f) {

	dp[x][siz[x] = 1] = 1;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == f ) continue;

		dfs(p->to, x);

		int t1 = siz[x], t2 = siz[p->to], del = 0;

		for(int i=2;i<=t2;i+=2)

			del = (del + 1LL*dp[p->to][i]*coef[i]%MOD) % MOD;

		del = (MOD - del) % MOD;

		for(int i=t1;i>=1;i--) {

			for(int j=t2;j>=1;j--)

				dp[x][i+j] = (dp[x][i+j] + 1LL*dp[x][i]*dp[p->to][j]%MOD) % MOD;

			dp[x][i] = 1LL*del*dp[x][i] % MOD;

		}

		siz[x] += siz[p->to];

	}

}



int main() {

	int N; init();

	scanf("%d", &N);

	for(int i=1;i<N;i++) {

		int x, y; scanf("%d%d", &x, &y);

		addedge(x, y);

	}

	dfs(1, 0);

	int ans = 0;

	for(int i=1;i<=N;i++)

		ans = (ans + 1LL*dp[1][i]*coef[i]%MOD) % MOD;

	printf("%d\n", ans);

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define re register

using namespace std;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=5000+10;

const int mod=1e9+7;



struct edge { int v,nxt; } e[N<<1];

int head[N];



inline void addEdge(int u,int v) {

    static int e_cnt=0;

    e[++e_cnt]=(edge){v,head[u]},head[u]=e_cnt;

}



int n,sz[N];

int f[N][N],g[N],tmp[N];



inline void dfs(int u,int fa) {

    sz[u]=f[u][1]=1;

    for (re int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v; if (v==fa) continue;

        dfs(v,u);

        for (re int j=1;j<=sz[u]+sz[v];++j) tmp[j]=0;

        for (re int j=1;j<=sz[u];++j)

            for (re int k=0;k<=sz[v];++k)

                tmp[j+k]=(tmp[j+k]+1ll*f[u][j]*f[v][k])%mod;

        sz[u]+=sz[v];

        for (re int j=1;j<=sz[u];++j) f[u][j]=tmp[j];

    }

    for (re int i=2;i<=sz[u];i+=2)

        f[u][0]=(f[u][0]-1ll*f[u][i]*g[i]%mod+mod)%mod;

}



int main() {

    n=read();

    for (re int i=1;i<n;++i) {

        int u=read(),v=read();

        addEdge(u,v),addEdge(v,u);

    }

    g[0]=1;

    for (re int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;

    dfs(1,0); printf("%d\n",mod-f[1][0]);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

	边覆盖与不覆盖作为状态非常不好 dp

	可能有多个点覆盖这条边然后就转移不了

	考虑容斥, 这样子我就可以只关注图的某种连通性了

	说到连通性 dp, 常见套路是枚举断不断父边, 然后就可以做了 

*/

#include <bits/stdc++.h>

#define N 5005



using namespace std;



const int mod = 1e9 + 7;



int n;

int head[N], nex[N << 1], to[N << 1], cntE;

int f[N][N], g[N], siz[N], tmp[N];



inline void addE(int u, int v) {

	to[++cntE] = v;

	nex[cntE] = head[u], head[u] = cntE;

}

void dfs(int u, int fa) {

	f[u][siz[u] = 1] = 1;

	for(int i = head[u], v; i; i = nex[i]) {

		v = to[i];

		if(v == fa) continue;

		dfs(v, u);

		memset(tmp, 0, sizeof tmp);

		for(int i = 1; i <= siz[u]; ++i)

			for(int j = 0; j <= siz[v]; ++j)

				tmp[i + j] = (tmp[i + j] + 1LL * f[u][i] * f[v][j]) % mod;

		siz[u] += siz[v];

		for(int i = 1; i <= siz[u]; ++i)

			f[u][i] = tmp[i];

	}

	for(int i = 2; i <= siz[u]; ++i)

		f[u][0] = (f[u][0] - 1LL * f[u][i] * g[i] % mod + mod) % mod;

}



int main() {

	scanf("%d", &n);

	for(int i = 1, u, v; i < n; ++i) {

		scanf("%d %d", &u, &v);

		addE(u, v), addE(v, u);

	}

	

	g[0] = 1;

	for(int i = 2; i <= n; i += 2)

		g[i] = (i - 1LL) * g[i - 2] % mod;

	

	dfs(1, 0);

	

	printf("%d\n", mod - f[1][0]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

const int N = 5003, mod = 1e9 + 7;

int n, head[N], to[N << 1], nxt[N << 1], siz[N], f[N][N], tmp[N], g[N];

inline void qmo(int &x){x += (x >> 31) & mod;}

inline void add(int a, int b){

    static int cnt = 0;

    to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;

}

inline void dfs(int x, int fa = 0){

    f[x][1] = siz[x] = 1;

    for(Rint i = head[x];i;i = nxt[i]) if(to[i] != fa){

        dfs(to[i], x);

        memcpy(tmp + 1, f[x] + 1, siz[x] << 2);

        memset(f[x] + 1, 0, siz[x] << 2);

        for(Rint j = 1;j <= siz[x];++ j)

            for(Rint k = 0;k <= siz[to[i]];++ k)

                qmo(f[x][j + k] += (LL) tmp[j] * f[to[i]][k] % mod - mod);

        siz[x] += siz[to[i]];

    }

    for(Rint i = 2;i <= siz[x];i += 2)

        qmo(f[x][0] -= (LL) f[x][i] * g[i] % mod);

}

int main(){

    scanf("%d", &n);

    for(Rint i = 1, u, v;i < n;++ i){

        scanf("%d%d", &u, &v); add(u, v); add(v, u);

    }

    g[0] = 1;

    for(Rint i = 2;i <= n;i += 2) g[i] = (i - 1ll) * g[i - 2] % mod;

    dfs(1); printf("%d\n", mod - f[1][0]);

}


// Optimized solution to the same problem (faster):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

// Fastest known solution for this problem: