【ARC063-E】木と整数

来源和评测点

ARC063-E

题目

【题目大意】
给出一棵N个节点的数,标号从1到N,第i(1≦i≦N−1)条边连接Ai和Bi。
Takahashi给K个节点填上数字,其它节点留空。
Aoki想把剩下的节点填好,并满足以下条件:
任意两个由一条边直接连接的节点,上面的数字差是1。
如果有多个解,输出一个即可。
Aoki填上的数字可能是负数或者比10^6大。
【输入格式】
N
A1 B1
A2 B2
:
AN−1 BN−1
K
V1 P1
V2 P2
:
VK PK
【约束条件】
1≦N≦10^5
1≦K≦N
1≦Ai,Bi≦N (1≦i≦N−1)
1≦Vj≦N (1≦j≦K)
0≦Pj≦10^5 (1≦j≦K)
给出的图一定是树。
所有vj不重复。
【输出格式】
用Yes或No表示是否有解。
如果有,输出N行,表示那个节点的某个合法值。
【输入样例】
5
1 2
3 1
4 3
3 5
2
2 6
5 7
【输出样例】
Yes
5
6
6
5
7

刷题记录

1h
2RE
1AC

分析

维护一个有效的范围和奇偶性,树形dp即可
然后数组漏了个0是什么鬼……

代码

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
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
//*******************全局常量*******************
const int MAXN=110000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct nod
{
int hou;
int val;
int mi,mx;
int jo;//-1,0,1
}p[MAXN];
struct edge
{
int y,g;
}e[2*MAXN];
//*******************实现*******************
int ln=0;
void ins(int x,int y)
{
ln++;
e[ln].y=y;
e[ln].g=p[x].hou;
p[x].hou=ln;
}
bool bk=1;
void dfs(int x,int fa)
{
if(bk==0) return;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(y==fa) continue;
dfs(y,x);
if(p[x].jo!=-1 and p[x].jo==p[y].jo)
{
bk=0;
return;
}//本来相邻或者递推得来
p[x].mi=mymax(p[x].mi,p[y].mi-1);
p[x].mx=mymin(p[x].mx,p[y].mx+1);
if(p[y].jo!=-1) p[x].jo=p[y].jo^1;//信息的合并
}
if(p[x].jo!=-1 and p[x].mi==p[x].mx and p[x].mi%2!=p[x].jo)
{
bk=0;
return;
}//检查
if(p[x].mi>p[x].mx)
{
bk=0;
return;
}
}
void dfs2(int x,int fa)
{
if(p[x].val==-1)
{
if(fa==0)
{
if(p[x].mi%2==p[x].jo) p[x].val=p[x].mi;
else p[x].val=p[x].mi+1;
}
else
{
if(p[x].mi<=p[fa].val-1 and p[fa].val-1<=p[x].mx) p[x].val=p[fa].val-1;//debug
else p[x].val=p[fa].val+1;
}
}
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(y==fa) continue;
dfs2(y,x);
}
}
//*******************主函数*******************
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
p[i].hou=0;
p[i].val=-1;
p[i].mi=-INF;p[i].mx=INF;
p[i].jo=-1;
}
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
int k;scanf("%d",&k);
for(int i=1;i<=k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
p[a].val=p[a].mi=p[a].mx=b;
p[a].jo=b%2;
}
dfs(1,0);//自下而上
if(bk==0) printf("No\n");
else
{
printf("Yes\n");
dfs2(1,0);//自上而下
for(int i=1;i<=n;i++) printf("%d\n",p[i].val);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e20b.html
转载请注明出处,谢谢!