Be in business
Title: NC14348
Time limit: C/C++ 1 second, 2 seconds for other languages
Space limitations: C/C++ 32768K, other languages 65536K
64bit IO Format: %lld
Title Description
Xiao d is a local tyrant in real estate. Everyone has the means to do business for everyone, of course, interpersonal relationships need to be placed first.
Every month, Xiao d needs to list a personal relationship table to show a network of people they work in real estate, but his energy is limited, so he can only communicate with the people he can contact. For example, if 1 knows 2, 2 knows 3, 1 can communicate with 3, of course, 1 and 2 can also communicate.
Little d is also savvy. He knows who he communicates with and gains a lot of benefits. Then he lists a list of benefits based on his own ideas to show how much energy he spends communicating with these people and what benefits he can get.
Little d wants to know exactly what benefits he can get within his energy range.
Set the number of Little d to 1. Limit the number of times a person has to interact to 1.
Enter a description:
This question contains multiple sets of inputs. The first line contains a number t, which represents the number of groups of test data. The first row of each set of data enters three numbers, N,M, C, to indicate how many people there are in this network, how many relationships there are in the network, and the energy value of small d. Next N-1 lines, two numbers ai, Bi per line. Line I here indicates that the person numbered i+1 knows that it takes ai's effort to get the benefit of bi. Next M lines, two numbers x, y per line, indicate that the person numbered x can contact the person numbered y t<=50 2<=N<=10000 1<=M<=10*N 1<=ai，bi<=10 1<=C<=500 1<=x,y<=N
Output description:
The output contains a line indicating the maximum benefit a small d can achieve
Example 1
input
1 5 3 7 5 10 3 2 4 3 1 100 1 2 2 3 1 4
output
10
Explain
The number of people Xiao Ming can reach is 234, so the best plan is to spend 5 energy to get 10 profit value for people with contact number 2.
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<list>
#include<set>
#include<iomanip>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cassert>
#include<sstream>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
const int N=5e4+7;
const int maxn=1e5+5;
const double EPS=1e-10;
const double Pi=3.1415926535897;
//inline double max(double a,double b){
// return a>b?a:b;
//}
//inline double min(double a,double b){
// return a<b?a:b;
//}
int xd[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int yd[8] = {1, 0, -1, 0, -1, 1, -1, 1};
//void Fire(){
// queue<node> p;
// p.push({fx,fy,0});
// memset(fire, -1, sizeof(fire));
// fire[fx][fy]=0;
// while(!p.empty()){
// node temp=p.front();
// p.pop();
// for(int i=0;i<8;i++){
// int x=temp.x+xd[i];
// int y=temp.y+yd[i];
// if(x<0||x>=n||y<0||y>=m||fire[x][y]!=-1){
// continue;
// }
// fire[x][y]=temp.val+1;
// p.push({x,y,temp.val+1});
// }
// }
//}
//int bfs(){
// queue<node> p;
// memset(vis, 0, sizeof(vis));
// p.push({sx,sy,0});
// while (!p.empty()) {
// node temp=p.front();
// vis[temp.x][temp.y]=1;
// p.pop();
// for(int i=0;i<4;i++){
// int x=temp.x+xd[i];
// int y=temp.y+yd[i];
// if(x<0||x>=n||y<0||y>=m) continue;
// if(x==ex&&y==ey&&temp.val+1<=fire[x][y]) return temp.val+1;
// if(vis[x][y]||temp.val+1>=fire[x][y]||a[x][y]=='#') continue;
// p.push({x,y,temp.val+1});
// }
// }
// return -1;
//}
//One-dimensional hash
//int n;
//string s;
//int bas=131;
//typedef unsigned long long ull;
//const ull mod1=100001651;
//ull a[100010];
//ull Hash(string s){
// ll ans=0;
// for(int i=0;i<s.size();i++){
// ans*=bas;
// ans+=int(s[i]);
// ans%=mod1;
// }
// return ans;
//}
//Two-dimensional hash
//using lom=unsigned long long ;
//const lom bas1=131,bas2=233;
//const int M=505;
//int n,m;
//char a[M][M];
//lom _hash[M][M];
//lom p1[M],p2[M];
//
//
//void init(){
// p1[0]=1;
// p2[0]=1;
// for(int i=1;i<=505;i++){
// p1[i]=p1[i-1]*bas1;
// p2[i]=p2[i-1]*bas2;
//
// }
//}
//void Hash(){
// _hash[0][0]=_hash[0][1]=_hash[1][0]=0;
// For(int i=1; i<=n; i++){//prefix and
// for(int j=1;j<=m;j++){
// _hash[i][j]=_hash[i][j-1]*bas1+a[i][j]-'a';
// }
// }
// For(int i=1; i<=n; i++){//2-D prefix and
// for(int j=1;j<=m;j++){
// _hash[i][j]+=_hash[i-1][j]*bas2;
// }
// }
//
//}
int t;
int n,m,c;
int x,y;
int dp[1001000];
int fa[1000010];//Array of fathers
int a[100010];//energy
int b[100010];//Profit
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void Union(int x,int y){
fa[find(x)]=find(y);
}
int main(){
cin>>t;
while (t--) {
cin>>n>>m>>c;
memset(dp, 0, sizeof(dp));
init();
for(int i=2;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=0;i<m;i++){
cin>>x>>y;
Union(x,y);
}
for(int i=2;i<=n;i++){
if(find(i)==find(1)){
for(int j=c;j>=a[i];j--){
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
}
cout<<dp[c]<<endl;
}
}