Pagini recente » Cod sursa (job #221190) | Cod sursa (job #1110508) | Statistici Lazurca Diana-Stefania (bluepink) | Cod sursa (job #2072303) | Cod sursa (job #1945913)
#include <fstream>
using namespace std;
ifstream f("treap.in");
ofstream g("treap.out");
#define nmax 150010
struct nod
{
int val;
nod *urm;
};
typedef nod *pnod;
pnod p,v[nmax];
int n;
void ad(int x,int y)
{
p=new nod;
p->val=y;
p->urm=v[x]->urm;
v[x]->urm=p;
}
bool bun[nmax],use[nmax];
int t[nmax],st[nmax],heap[nmax],abc[nmax];
int first[nmax],last[nmax];
struct arbc
{
int val;
arbc *as,*ad;
};
typedef arbc *parbc;
int to=0;
void bfs(int inc)
{
pnod p;
p=v[inc]->urm;
use[inc]=1;
to+=1;
first[inc]=to;
while(p)
{
if(use[p->val]==0)
{
v[p->val]->val-=1;
t[p->val]=inc;
bfs(p->val);
}
p=p->urm;
}
to+=1;
last[inc]=to;
}
int cresc[nmax];
void bunheap()
{
int i;
for(i=1;i<=n;i++)
{
if(bun[i]==1)
{
p=v[i]->urm;
if(p)
{
if(t[i]!=p->val and heap[i]<heap[p->val])
bun[i]=0;
if(p->urm and t[i]!=p->urm->val and heap[i]<heap[p->urm->val])
bun[i]=0;
}
}
}
}
parbc creeaza(int rad)
{
pnod p;
p=v[rad]->urm;
int a=0,b=0;
parbc ass=0,add=0,w,q;
while(p)
{
if(t[rad]!=p->val)
{
w=creeaza(p->val);
if(a)
{
b=p->val;
add=w;
}
else
{
a=p->val;
ass=w;
}
}
p=p->urm;
}
q=new arbc;
q->val=rad;
q->as=ass;
q->ad=add;
return q;
}
void srd(parbc rad)
{
if(rad)
{
srd(rad->as);
to+=1;
cresc[to]=abc[rad->val];
srd(rad->ad);
}
}
int main()
{
parbc rad;
int i,x,y,j;
f>>n;
for(i=1;i<=n;i++)
{
v[i]=new nod;
v[i]->urm=0;
v[i]->val=0;
bun[i]=1;
}
for(i=1;i<n;i++)
{
f>>x>>y;
ad(x,y);
ad(y,x);
v[x]->val+=1;
v[y]->val+=1;
}
for(i=1;i<=n;i++)
{
f>>abc[i];
}
for(i=1;i<=n;i++)
{
f>>heap[i];
}
bfs(1);
for(i=1;i<=n;i++)
{
if(v[i]->val>2)
bun[i]=0;
}
bunheap();
rad=creeaza(1);
to=0;
srd(rad);
for(i=2;i<=n;i++)
{
if(cresc[i-1]>cresc[i])
{
if(first[i-1]<first[i] and last[i]<last[i-1])
{
bun[t[i]]=0;
}
else
bun[t[i-1]]=0;
}
}
for(i=2;i<=n;i++)
{
if(bun[i]==0)
{
j=t[i];
while(j and bun[j]==1)
{
bun[j]=0;
j=t[j];
}
}
}
for(i=1;i<=n;i++)
g<<bun[i]<<" ";
return 0;
}