Pagini recente » Cod sursa (job #1101225) | Cod sursa (job #2850571) | Cod sursa (job #630009) | Cod sursa (job #829742) | Cod sursa (job #586271)
Cod sursa(job #586271)
#include<stdio.h>
#include<vector>
using namespace std;
#define maxN 200005
FILE*f=fopen("guvern.in","r");
FILE*g=fopen("guvern.out","w");
vector<int>A[maxN];
int n,i,Niv[maxN],Viz[maxN],Coop[maxN],Nec[maxN],x,y,Min,nodmin,X[maxN],Fr[maxN],k,Nr,maxsub,nsol;
int maxx;
void dfs1(int nod,int niv){
Niv[nod] = niv;
Viz[nod] = 1;
int nrsub = 0;
for ( int i = 0 ; i < A[nod].size () ; ++i ){
if ( !Viz[A[nod][i]] ){
++nrsub;
dfs1(A[nod][i],niv+1);
}
}
if ( !nrsub ){
Fr[++k] = nod;
}
}
void dfs2(int nod){
if ( nod != i && nod != 1 ){
if ( Coop[nod] < Min && Coop[nod] >= Coop[i] )
Min = Coop[nod],nodmin = nod;
}
for ( int i = 0 ; i < A[nod].size() ; ++i ){
if ( Niv[A[nod][i]] < Niv[nod] ){
dfs2(A[nod][i]);
}
}
}
void dfs3(int nod ){
if ( X[nod] ) maxsub = maxsub > Coop[nod] ? maxsub : Coop[nod];
for ( int i = 0 ; i < A[nod].size () ; ++i ){
int vcn = A[nod][i];
if ( Niv[vcn] > Niv[nod] )
dfs3(vcn);
}
}
inline int maxsubarb ( int nod ){
maxsub = 0;
dfs3(nod);
return maxsub;
}
bool solutie () {
int i;
for ( i = 1 ; i <= n ; ++i ){
if ( Nec[i] != -1 && !X[Nec[i]] && X[i] )
return 0;
}
for ( i = 1 ; i <= n ; ++i ){
if ( !X[i] ) continue;
if ( maxsubarb(i) > Coop[i] )
return 0;
}
return 1;
}
void back( int niv ){
if ( niv == n + 1 ){
/*int ok = 0;
for ( int i = 1 ; i <= n ; ++i ){
if ( (i == 3 || i == 7 || i == 9 || i == 1) && !X[i] ){
ok = 1;
}
if ( X[i] && i != 3 && i != 7 && i != 9 && i != 1 )
ok = 1;
}
if ( !ok ){
fprintf(g,"%d\n",Nr);
}
*/
if ( Nr > maxx ){
if ( solutie() ){
maxx = Nr;
nsol = 1;
}
}
else{
if( Nr == maxx && solutie() )
++nsol;
}
return ;
}
for ( int i = 0 ; i <= 1 ; ++i ){
X[niv] = i;
if ( i ) ++Nr;
back(niv+1);
if ( i ) --Nr;
}
}
int main () {
fscanf(f,"%d",&n);
for ( i = 1 ; i < n ; ++i ){
fscanf ( f, "%d %d",&x,&y) ;
A[x].push_back(y);
A[y].push_back(x);
}
for ( i = 1 ; i <= n ; ++i ){
fscanf(f,"%d",&Coop[i]);
}
dfs1(1,0); for ( i = 1 ; i <= n ; ++i ){ Viz[i] = 0; }
Nec[1] = -1;
for ( i = 2 ; i <= n ; ++i ){
Min = 1 << 29;
dfs2(i);
Nec[i] = (Min == 1 << 29 ? -1 : nodmin);
}
back(1);
fprintf(g,"%d\n%d",maxx,nsol);
fclose(f);
fclose(g);
return 0;
}