题解

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN=100000;
vector<int> g[MAXN+2];
int n,m;
int fa[MAXN+2][20],depth[MAXN+2];
void BuildTree(int x){
for(int i=0,len=g[x].size(),y;i^len;++i){
y=g[x][i];
if(y^fa[x][0]){
fa[y][0]=x;
depth[y]=depth[x]+1;
BuildTree(y);
}
}
}
void prepare_lca(){
for(int j=1;j^20;++j)
for(int i=1;i<=n;++i)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
int get_lca(int a,int b){
if(depth[a]<depth[b])
swap(a,b);
for(int j=19;~j;--j)
if((depth[a]-depth[b])>>j&1)
a=fa[a][j];
if(a==b)
return a;
for(int j=19;~j;--j)
if(fa[a][j]!=fa[b][j])
a=fa[a][j],b=fa[b][j];
return fa[a][0];
}
int jump_close(int a,int b){
for(int j=19;~j;--j)
if(depth[fa[a][j]]>depth[b])
a=fa[a][j];
return a;
}
int Down[MAXN+2];bool ans[MAXN+2];
void get_ans(int x,int sum){
if((sum+=Down[x])>=0) ans[x]=1;
for(int i=0,len=g[x].size(),y;i^len;++i){
y=g[x][i];
if(y^fa[x][0])
get_ans(y,sum);
}
}
vector<int> earlier[MAXN+2];
int rd[MAXN+2];queue<int> q;
bool GetTopOrder(){
for(int i=1;i<=n;++i)
if(rd[i]==1){
rd[i]=0;
q.push(i);
}
int x;
while(!q.empty()){
x=q.front(),q.pop();
for(int i=0,len=g[x].size();i^len;++i)
if(--rd[g[x][i]]==1){
rd[g[x][i]]=0;
q.push(g[x][i]);
}
for(int i=0,len=earlier[x].size();i^len;++i)
if(--rd[earlier[x][i]]==1){
rd[earlier[x][i]]=0;
q.push(earlier[x][i]);
}
}
for(int i=1;i<=n;++i)
if(rd[i]>0)
return false;
return true;
}
bool check_NoSolution(){
for(int i=1;i<=n;++i){
for(int j=0,len=g[i].size();j^len;++j)
++rd[g[i][j]];
for(int j=0,len=earlier[i].size();j^len;++j)
++rd[earlier[i][j]];
}
return !GetTopOrder();
}

int main()
{
scanf("%d %d",&n,&m);
for(int i=1,x,y;i^n;++i){
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
BuildTree(1);
prepare_lca();
for(int i=0,a,b;i^m;++i){
scanf("%d %d",&a,&b);
earlier[a].push_back(b);
int lca=get_lca(a,b);
if(lca==a){
--Down[1];
++Down[jump_close(b,a)];
}
else
--Down[a];
}
if(check_NoSolution())
--Down[1];
get_ans(1,0);
for(int i=1;i<=n;++i){
putchar((ans[i]?1:0)+'0');
puts("");
}
return 0;
}