2019 BUAA Spring Training 5 题解

发表于 | 更新于 | 评论数： | 阅读次数：
Solved A B C D E
5/5 Ø O Ø Ø O
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

比赛链接

A

题目描述

现有一棵 $n$ 个点的树，每条边 $i$ 都一个边权 $w_i$，接下来有 $m$ 个操作：
第一种操作给出两个点 $a_i$,$ b_i$，一个数 $y_i$：从 $a_i$ 沿最短路走到 $b_i$ 的过程中，每经过一条边 $j$，就将 $y_i$ 除以边权 $w_j$ 并向下取整，即进行 $y_i=\lfloor\frac{y_i}{w_j}\rfloor $ ，输出走完后的 $y_i$。
第二种操作给出某条边 $e_i$，一个数 $c_i$，满足 $c_i$ < $w_{e_i}$：将 $e_i$ 边权修改为 $c_i$。

解题思路

刚开始傻乎乎瞎改点剖模板然后$T$了。

TLE代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<cstdio>
#include<algorithm>
#define N 200010
int n,m,r,mod;
double a[N];
int count=2,head[N];
struct Edge{
    int end,near,sign;
    double len;
}edge[2*N];
void addedge(int begin,int end,double len){
    edge[count].end=end;
    edge[count].near=head[begin];
    edge[count].len=len;
    head[begin]=count++;
}
int depth[N],fa[N],size[N],son[N],pos[N],top[N];
double temp[N],sonlen[N];
int cnt;
struct Tree{
    int left,right;
    double data;
}tree[4*N];
void build(int p,int left,int right){
    tree[p].left=left;
    tree[p].right=right;
    if(left==right){
        tree[p].data=temp[left];
        return;
    }
    build(p<<1,left,(left+right)>>1);
    build(p<<1|1,((left+right)>>1)+1,right);
    tree[p].data=tree[p<<1].data*tree[p<<1|1].data;
}
double query(int p,int left,int right){
    int l=tree[p].left,r=tree[p].right;
    if(l>=left&&r<=right)return tree[p].data;
    if(r<left||l>right)return 1;
    return query(p<<1,left,right)*query(p<<1|1,left,right);
}
void dfs1(int now,int f,int dep){
    depth[now]=dep;
    fa[now]=f;
    size[now]=1;
    int i,max=0;
    for(i=head[now];i;i=edge[i].near){
        int p=edge[i].end;
        if(p!=f){
            edge[i].sign=1;
            dfs1(p,now,dep+1);
            size[now]+=size[p];
            if(size[p]>max){
                max=size[p];
                son[now]=p;
                sonlen[now]=edge[i].len;
            }
        }
    }
}
void dfs2(int now,int Top,double x){
    int i;
    pos[now]=++cnt;
    temp[cnt]=x;
    top[now]=Top;
    if(!son[now])return;
    dfs2(son[now],Top,sonlen[now]);
    for(i=head[now];i;i=edge[i].near){
        int p=edge[i].end;
        if(p-son[now]&&p-fa[now])dfs2(p,p,edge[i].len);
    }
}
int bot[N],mxd[N];
void dfs3(int p,int f){
    int i,tmp=p;
    mxd[p]=depth[p];
    for(i=head[p];i;i=edge[i].near){
        int q=edge[i].end;
        if(q==f)continue;
        dfs3(q,p);
        if(mxd[q]>mxd[p])mxd[p]=mxd[q],tmp=bot[q];
    }
    bot[p]=tmp;
}
double rangequery(double fir,int x,int y){
    double ans=fir;
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]])std::swap(x,y);
        ans/=query(1,pos[top[x]],pos[x]);
        if(ans<1)return 0;
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])std::swap(x,y);
    return ans/query(1,pos[x],pos[y]);
}
int d[N],Fa[22][N],lg[N];
void dfs(int now,int f){
    d[now]=d[f]+1;
    Fa[0][now]=f;
    int i;
    for(i=1;(1<<i)<=d[now];i++)Fa[i][now]=Fa[i-1][Fa[i-1][now]];
    for(i=head[now];i;i=edge[i].near){
        int p=edge[i].end;
        if(p!=f)dfs(p,now);
    }
}
int lca(int x,int y){
    int i;
    if(d[x]<d[y]){int t=x;x=y;y=t;}
    while(d[x]>d[y])x=Fa[lg[d[x]-d[y]]][x];
    if(x==y)return x;
    for(i=lg[d[x]];~i;i--)if(Fa[i][x]!=Fa[i][y])x=Fa[i][x],y=Fa[i][y];
    return Fa[0][x];
}
void modify(int l,int r,int p,double change,int inin){
    if(tree[p].left<=inin&&inin<=tree[p].right)tree[p].data*=change;
    if(tree[p].left==tree[p].right&&tree[p].left==1)tree[p].data=1;
    if(tree[p].left>r||tree[p].right<l||p>4*n)return;
    modify(l,r,p<<1,change,inin);
    modify(l,r,p<<1|1,change,inin);
}
int main(){
    int i,x,y,sign,r=1;
    double w;
    scanf("%d%d",&n,&m);
    for(i=1;i<n;i++){
        scanf("%d%d%lf",&x,&y,&w);
        addedge(x,y,w);addedge(y,x,w);
    }
    dfs(r,0);
    for(i=2;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
    dfs1(r,0,1);
    dfs2(r,r,1);
    dfs3(r,0);
    build(1,1,n);
    temp[pos[1]]=1;
    for(i=0;i<m;i++){
        scanf("%d",&sign);
        if(sign==1){
            double y;int a,b;
            scanf("%d%d%lf",&a,&b,&y);
            int ff=lca(a,b);
            double rq=rangequery(y*temp[pos[ff]],a,b);
            printf("%I64d\n",(long long)(1e-8+rq));
        }else{
            int a;double b;
            scanf("%d%lf",&a,&b);a<<=1;
            int p=edge[a].sign?edge[a].end:edge[a^1].end,q=p,tmp=p;
            p=top[p];q=bot[q];
            p=pos[p];q=pos[q];
            if(p>q)std::swap(p,q);
            double change=b/edge[a].len;
            modify(p,q,1,change,pos[tmp]);
        }
    }
    return 0;
}

考虑每次边权只能减小，每次将权值为$1$的路径用并查集合并起来即可。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
typedef long long ll;
#define N 200010
struct Edge{
    int e,n,i;
    ll len;
}e[N<<1];
int hd[N],cnt=1,n,m;
void add(int a,int b,ll w,int i){
    e[++cnt].e=b;e[cnt].n=hd[a];e[cnt].len=w;e[cnt].i=i;hd[a]=cnt;
}
int fa[N],dep[N],to[N];
ll up[N];
void dfs(int p,int d){
    dep[p]=d;
    int i;
    for(i=hd[p];i;i=e[i].n){
        int q=e[i].e;
        if(q==fa[p])continue;
        fa[q]=p;
        up[q]=e[i].len;
        to[e[i].i]=q;
        dfs(q,d+1);
    }
}
int f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
ll solve(int u,int v,ll w){
    u=find(u),v=find(v);
    while(u!=v){
        if(dep[u]<dep[v])std::swap(u,v);
        w/=up[u];
        if(!w)return 0;
        u=find(fa[u]);
    }
    return w;
}
int main(){
    int i,u,v,opt;
    ll w;
    scanf("%d%d",&n,&m);
    for(i=1;i<n;i++){
        scanf("%d%d%I64d",&u,&v,&w);
        add(u,v,w,i),add(v,u,w,i);
        f[i]=i;
    }f[n]=n;
    dfs(1,0);
    for(i=1;i<=n;i++)if(up[i]==1)f[i]=find(fa[i]);
    for(i=0;i<m;i++){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%I64d",&u,&v,&w);
            printf("%I64d\n",solve(u,v,w));
        }else{
            scanf("%d%I64d",&u,&w);
            up[to[u]]=w;
            if(w==1)f[to[u]]=find(fa[to[u]]);
        }
    }
    return 0;
}

B

题目描述

现有一棵$n$个点的树，点的编号从 $1$ 起，树以 $1$ 为根，每个点 $i$ 都一个颜色 $c_i$，接下来有$m$个询问，每次询问以 $v_j$ 为根的子树中，求有多少种颜色，这些颜色在子树中出现的次数至少为 $k_j$。

解题思路

树上莫队裸题。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define N 100010
struct Edge{
    int e,n;
}e[N<<1];
int block;
struct DFN{
    int l,r;
}dfn[N];
int hd[N],cnt,n,m;
void add(int a,int b){e[++cnt].n=hd[a],e[cnt].e=b,hd[a]=cnt;}
int tot=1;
int count[N],seq[N];
void dfs(int p){
    dfn[p].l=tot;
    seq[tot]=p;
    tot++;
    int i;
    for(i=hd[p];i;i=e[i].n){
        int q=e[i].e;
        if(!dfn[q].l)dfs(q);
    }
    dfn[p].r=tot-1;
}
int getblock(int x){
    return x/block;
}
struct Query{
    int p,k,i;
    bool operator<(const Query &a)const{
        int l=dfn[p].l,r=dfn[p].r,L=dfn[a.p].l,R=dfn[a.p].r;
        return getblock(l)==getblock(L)?getblock(r)<getblock(R):getblock(l)<getblock(L);
    }
}q[N];
int color[N],sum[N],a[N];
void del(int x){
    --sum[count[color[seq[x]]]--];
}
void add(int x){
    ++sum[++count[color[seq[x]]]];
}
int ans[N];
int main(){
    int i,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&color[i]);
    for(i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dfs(1);
    block=n/sqrt(n);
    for(i=1;i<=m;i++)scanf("%d%d",&q[i].p,&q[i].k),q[i].i=i;
    std::sort(q+1,q+1+m);
    int l=1,r=0;
    for(i=1;i<=m;i++){
        int L=dfn[q[i].p].l,R=dfn[q[i].p].r;
        while(l>L)add(--l);
        while(r<R)add(++r);
        while(l<L)del(l++);
        while(r>R)del(r--);
        ans[q[i].i]=sum[q[i].k];
    }
    for(i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

C

题目描述

现有一个 $n$ 个点、$m$ 条边的连通无向图，点的编号从 $1$ 起，每条边都有一个边权。图没有重边，也没有自环。

接下来对每条边单独考虑，需要重新设定这条边的边权，使得它绝对能够出现在所有的最小生成树中。

请你对每条边，在满足题意的情况下，可以重新设定的最大边权。

解题思路

太神仙了。

先求出最小生成树，然后对于每一个非树边$[start,end]$必然在最小生成树内的充要条件是该边边权比最小生成树中这两点$(start,end)$之间所有边的最大值小，对于每一个树边$[start,end]$必然在最小生成树内的充要条件是该边边权比$start$为根的子树与$end$为根的子树中任意两个点之间连边的边权小。

于是问题就转化成了：对于每一个非树边，求出$[start,end]$路径中的最小值，并更新$[start,end]$路径中所有边对应答案的最小值。显然树剖可做。（就是有点难写）

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<bits/stdc++.h>
#define N 200010
int temp[N];
struct Edge{
    int b,e,n,l,i;
    bool operator<(const Edge&a)const{
        return l<a.l;
    }
}ed[N<<1],e[N<<1];
int sign[N];//是否为MST边
int hd[N],cnt;
int n,m;
void add(int a,int b,int l,int i){
    e[++cnt].e=b,e[cnt].b=a,e[cnt].l=l,e[cnt].i=i,e[cnt].n=hd[a],hd[a]=cnt;
}
int F[N];
int find(int x){return x==F[x]?x:F[x]=find(F[x]);}
struct segtree{
    int mn,mx,l,r,lazy;
}t[N<<2];
int inf=1.2e9;
int dep[N],siz[N],son[N],fa[N],lento[N];
int pre[N];
void dfs1(int p,int f,int d){
    int i,mx=0;
    fa[p]=f;
    dep[p]=d;
    siz[p]=1;
    for(i=hd[p];i;i=e[i].n){
        int q=e[i].e;
        if(q==f)continue;
        dfs1(q,p,d+1);
        siz[p]+=siz[q];
        lento[q]=e[i].l;
        pre[q]=e[i].i;
        if(siz[q]>mx){
            mx=siz[q];
            son[p]=q;
        }
    }
}
int top[N],pos[N],count;
void dfs2(int p,int Top){
    int i;
    pos[p]=++count;
    temp[count]=lento[p];
    top[p]=Top;
    if(!son[p])return;
    dfs2(son[p],Top);
    for(i=hd[p];i;i=e[i].n){
        int q=e[i].e;
        if(q!=son[p]&&q!=fa[p])dfs2(q,q);
    }
}
void krustal(){
    int i;
    for(i=1;i<=n;i++)F[i]=i;
    for(i=1;i<=m;i++){
        int st,fn,p=ed[i].e,q=ed[i].b;
        if((st=find(p))==(fn=find(q)))continue;
        sign[ed[i].i]=1;
        add(p,q,ed[i].l,ed[i].i);
        add(q,p,ed[i].l,ed[i].i);
        F[st]=fn;
    }
}
//segt
void update(int p){
    t[p].mn=std::min(t[p<<1].mn,t[p<<1|1].mn);
    t[p].mx=std::max(t[p<<1].mx,t[p<<1|1].mx);
}
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].mn=t[p].lazy=inf;
    if(l==r){
        t[p].mx=temp[l];
        return;
    }
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
    update(p);
}
void pushdown(int p){
    int lazy=t[p].lazy;
    t[p<<1].mn=std::min(t[p<<1].mn,lazy);
    t[p<<1].lazy=std::min(t[p<<1].lazy,lazy);
    t[p<<1|1].mn=std::min(t[p<<1|1].mn,lazy);
    t[p<<1|1].lazy=std::min(t[p<<1|1].lazy,lazy);
    t[p].lazy=inf;
}
int querymax(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    pushdown(p);
    if(l<=L&&R<=r)return t[p].mx;
    if(l>R||r<L)return 0;
    return std::max(querymax(p<<1,l,r),querymax(p<<1|1,l,r));
}
int querymin(int p,int Pos){
    int L=t[p].l,R=t[p].r;
    pushdown(p);
    if(Pos==L&&R==Pos)return t[p].mn;
    if(Pos>R||Pos<L)return inf;
    return std::min(querymin(p<<1,Pos),querymin(p<<1|1,Pos));
}
void modifymin(int p,int l,int r,int w){
    int L=t[p].l,R=t[p].r;
    pushdown(p);
    if(l<=L&&r>=R){
        t[p].mn=std::min(t[p].mn,w);
        t[p].lazy=std::min(t[p].lazy,w);
        return;
    }
    if(l>R||r<L)return;
    modifymin(p<<1,l,r,w);
    modifymin(p<<1|1,l,r,w);
    update(p);
}
//endsegt
int ans[N];
int rangequerymax(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])std::swap(x,y);
        ans=std::max(ans,querymax(1,pos[top[x]],pos[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])std::swap(x,y);
    return std::max(ans,querymax(1,pos[y]+1,pos[x]));//!
}
void rangemodifymin(int x,int y,int w){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])std::swap(x,y);
        modifymin(1,pos[top[x]],pos[x],w);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])std::swap(x,y);
    modifymin(1,pos[y]+1,pos[x],w);//!
}
void print(int p){
    printf("t[%2d]:%2d %2d %2d %2d %2d\n",p,t[p].l,t[p].r,t[p].mn>1000?-1:t[p].mn,t[p].mx>1000?t[p].mx:-1,t[p].lazy>1000?-1:t[p].lazy);
    if(t[p].l==t[p].r)return;
    print(p<<1);
    print(p<<1|1);
}
int main(){
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)scanf("%d%d%d",&ed[i].b,&ed[i].e,&ed[i].l),ed[i].i=i;
    std::sort(ed+1,ed+m+1);
    krustal();
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    for(i=1;i<=m;i++)if(!sign[ed[i].i]){
        ans[ed[i].i]=rangequerymax(ed[i].b,ed[i].e)-1;
        rangemodifymin(ed[i].b,ed[i].e,ed[i].l);
        //print(1);puts("");
    }
    for(i=2;i<=n;i++)ans[pre[i]]=querymin(1,pos[i])-1;
    for(i=1;i<=m;i++)printf("%d ",ans[i]<=1e9?ans[i]:-1);
    return 0;
}

D

题目描述

给一棵 $n$ 个节点为红蓝两色的树，节点标号从 $1$ 开始，其中 $1$ 号节点为红色，其它节点为蓝色，要求支持如下操作：

  1. 选择一个节点变为红色
  2. 查询一个节点到最近红色节点的距离

解题思路

怎么还有这种操作$.jpg$

储存超过$sqrt(n)$个红点的时候暴力$bfs$重置，询问的时候暴力计算距离。复杂度$O(a\sqrt n+blogn)$，$a,b$分别为操作$1,2$的个数。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define N 100002
struct Edge{
    int e,n;
}e[N<<1];
int hd[N],cnt;
void add(int a,int b){
    e[++cnt].e=b;
    e[cnt].n=hd[a];
    hd[a]=cnt;
}
int siz,n,m;
int sta[N],top;
int dis[N];
queue<pair<int,int>>Q;
void bfs(){
    int i;
    for(i=1;i<=top;i++)Q.push(make_pair(sta[i],0)),dis[sta[i]]=0;
    while(!Q.empty()){
        int p=Q.front().first,d=Q.front().second+1;Q.pop();
        for(i=hd[p];i;i=e[i].n)
            if(dis[e[i].e]>d)dis[e[i].e]=d,Q.push(make_pair(e[i].e,d));
    }
    top=0;
}
int d[N],fa[22][N],lg[N];
void dfs(int now,int f){
    dis[now]=dis[f]+1;
    d[now]=d[f]+1;
    fa[0][now]=f;
    int i;
    for(i=1;(1<<i)<=d[now];i++)fa[i][now]=fa[i-1][fa[i-1][now]];
    for(i=hd[now];i;i=e[i].n){
        int p=e[i].e;
        if(p!=f)dfs(p,now);
    }
}
int lca(int x,int y){
    int i;
    if(d[x]<d[y]){int t=x;x=y;y=t;}
    while(d[x]>d[y])x=fa[lg[d[x]-d[y]]][x];
    if(x==y)return x;
    for(i=lg[d[x]];~i;i--)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
int main(){
    int i,t,v,u;
    scanf("%d%d",&n,&m);
    siz=sqrt(n)+1;
    for(i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(i=2;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
    dis[0]=-1;
    dfs(1,0);
    while(m--){
        scanf("%d%d",&t,&v);
        if(t==1){
            sta[++top]=v;
            if(siz==top)bfs();
        }else{
            int ans=dis[v];
            for(i=1;i<=top;i++)ans=min(ans,d[v]+d[sta[i]]-2*d[lca(v,sta[i])]);
            printf("%d\n",ans);
        }
    }
    return 0;
}

E

题目描述

给定一棵点权为$0/1$的，以编号 $1$ 的节点为根的树。对每个点$x$可以进行如下操作，把自己的点权异或上$1$，把自己儿子的点权异或上$0$ ， 把儿子的儿子点权异或上$1$，依次类推；即$x$子树中，距离$x$为偶数的点的点权均异或上$1$。

求最少操作次数，使得每个点的点权全部变成给定的一组目标点权。

解题思路

暴力从根向下贪心即可。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
int n;
#define N 100010
struct Edge{
    int end,near;
}e[N<<1];
int cnt,head[N];
void add(int a,int b){
    e[++cnt].end=b;e[cnt].near=head[a];head[a]=cnt;
}
int tar[N],fir[N],ans;
int sta[N];
void solve(int p,int flag,int nxt,int f){
    int i;
    if((tar[p]^flag)!=fir[p])sta[ans++]=p;
    if(nxt==0){
        if(tar[p]!=fir[p])nxt=1,flag=0;
    }else if(nxt==1){
        if(tar[p]!=fir[p]){
            if(flag)flag=0;
            else nxt=2,flag=1;
        }else{
            if(flag)nxt=flag=0;
            else flag=1;
        }
    }else{
        if(tar[p]==fir[p])flag=nxt=1;
    }
    for(i=head[p];i;i=e[i].near){
        int q=e[i].end;
        if(q==f)continue;
        solve(q,flag,nxt,p);
    }
}
int main(){
    int i,u,v;
    scanf("%d",&n);
    for(i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(i=1;i<=n;i++)scanf("%d",&fir[i]);
    for(i=1;i<=n;i++)scanf("%d",&tar[i]);
    solve(1,0,0,0);
    printf("%d\n",ans);
    for(i=0;i<ans;i++)printf("%d\n",sta[i]);
    return 0;
}