大家好,又见面了,我是你们的朋友全栈君。
https://www.nowcoder.com/acm/contest/206/I
黄YY是一个清明梦超能力者,同时也是一个记忆大师。他能够轻松控制自己在梦中的一切,在醒来之后还能清晰的记得梦中所有的细节,这让他的朋友们都十分羡慕。 又是一个晚上,黄YY又到了自己的梦中,并且随手造出了一棵有n个点的树,树上每个点有一个初始颜色0。为了让这棵树不那么单调,黄YY拿起了画笔在上面尽情上色。每一次上色可以用u, v, c来描述,代表黄YY把u, v这条路径上的点都染色成了c。 正当黄YY开心的完成了m次染色,准备在早上醒来之时向朋友们炫耀。但现实中的黄YY由于过于兴奋滚到了床下,撞到了脑袋,在剧痛中醒来。由于脑部受到了严重创伤,黄YY对刚才梦境中发生的一切发生了严重的信息丢失。 但英俊潇洒的黄YY当然不希望自己的窘态被朋友们发现。为了证明自己还是那个清明梦超能力者,他希望告诉朋友们自己上色后每个节点的颜色。同时为了更进一步证明他还是个记忆大师,他希望干脆直接说出每个点在倒数第k次染色时的颜色。 当然,现在的黄YY已经成了弱智了,作为黄YY最亲密的朋友,你快来帮帮黄YY吧!
第一行三个整数n, m, k,代表树的点数,黄YY染色的次数,以及最后求颜色时,倒数的次数(1 ≤ n, m, k ≤ 100000)。
接下来n - 1行,每行u, v代表u, v两点之间有一条边。这里保证1 ≤ u, v
≤ n,且无重边与自环,是一棵标准的树。
接下来m行,每一行三个数字u, v, c代表黄YY在第这次用c颜色的画笔从u涂到了v。
一行$n$个数字,输出每个点倒数第$k$次染色时的颜色。如果本身不足$k$次,输出0。
示例1
3 3 2
1 2
2 3
1 2 1
2 3 2
1 3 3
1 2 2
对于点1在第一次和第三次染色的时候分别被染色为1, 3,倒数第二次的颜色就是1。
对于点2在第一、二、三次染色的时候分别被染色为1, 2, 3,倒数第二次的颜色就是2。
对于点3在第二次和第三次染色的时候分别被染色为2, 3,倒数第二次的颜色就是2。
因为要求倒数第k个颜色,所以可以逆着染色。
要注意的是,要用个idx数组标记线段树的某个位置是对应原来数组的哪个位置
1 #include<iostream>
2 #include<cstring>
3 #include<string>
4 #include<cmath>
5 #include<cstdio>
6 #include<algorithm>
7 #include<vector>
8 #define maxn 200005
9 #define lson l,mid,rt<<1
10 #define rson mid+1,r,rt<<1|1
11 using namespace std;
12 int tree[maxn<<3],lazy[maxn<<3];
13 int n;
14 int v[maxn],val[maxn],idx[maxn];
15 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt;
16 vector<int>ve[maxn];
17 int ans[maxn];
18
19 void push_up(int rt){
20 tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
21 }
22
23 void push_down(int rt){
24 if(lazy[rt]){
25 lazy[rt<<1]+=lazy[rt];
26 lazy[rt<<1|1]+=lazy[rt];
27 tree[rt<<1]-=lazy[rt];
28 tree[rt<<1|1]-=lazy[rt];
29 lazy[rt]=0;
30 }
31 }
32
33 void build(int k,int l,int r,int rt){
34 lazy[rt]=0;
35 tree[rt]=k;
36 if(l==r) return;
37 int mid=(l+r)/2;
38 build(k,lson);
39 build(k,rson);
40 }
41
42 void query(int k,int l,int r,int rt){
43 if(tree[rt]>0) return;
44 if(l==r){
45 ans[idx[l]]=k;
46 tree[rt]=0x3f3f3f3f;
47 return;
48 }
49 int mid=(l+r)/2;
50 push_down(rt);
51 query(k,lson);
52 query(k,rson);
53 push_up(rt);
54 }
55
56 void add(int L,int R,int k,int l,int r,int rt){
57 if(L<=l&&R>=r){
58 tree[rt]--;
59 lazy[rt]++;
60 query(k,l,r,rt);
61 return;
62 }
63 int mid=(l+r)/2;
64 push_down(rt);
65 if(L<=mid) add(L,R,k,lson);
66 if(R>mid) add(L,R,k,rson);
67 push_up(rt);
68 }
69
70 void dfs1(int now,int f,int deep){
71 dep[now]=deep;
72 siz[now]=1;
73 fa[now]=f;
74 int maxson=-1;
75 for(int i=0;i<ve[now].size();i++){
76 if(ve[now][i]==f) continue;
77 dfs1(ve[now][i],now,deep+1);
78 siz[now]+=siz[ve[now][i]];
79 if(siz[ve[now][i]]>maxson){
80 maxson=siz[ve[now][i]];
81 son[now]=ve[now][i];
82 }
83 }
84 }
85
86 void dfs2(int now,int topp){
87 id[now]=++cnt;
88 idx[cnt]=now;///!!!重点
89 val[cnt]=v[now];
90 top[now]=topp;
91 if(!son[now]) return;
92 dfs2(son[now],topp);
93 for(int i=0;i<ve[now].size();i++){
94 if(ve[now][i]==son[now]||ve[now][i]==fa[now]) continue;
95 dfs2(ve[now][i],ve[now][i]);
96 }
97 }
98
99
100 void addRange(int x,int y,int k){
101 while(top[x]!=top[y]){
102 if(dep[top[x]]<dep[top[y]]) swap(x,y);
103 add(id[top[x]],id[x],k,1,n,1);
104 x=fa[top[x]];
105 }
106 if(dep[x]>dep[y]) swap(x,y);
107 add(id[x],id[y],k,1,n,1);
108 }
109
110 struct Option{
111 int x,y,v;
112 }p[100005];
113
114 int main(){
115 std::ios::sync_with_stdio(false);
116 int m,r;
117 int k;
118 cin>>n>>m>>k;
119 int pos,z,x,y;
120 for(int i=1;i<n;i++){
121 cin>>x>>y;
122 ve[x].push_back(y);
123 ve[y].push_back(x);
124 }
125 cnt=0;
126 dfs1(1,0,1);
127 dfs2(1,1);
128 build(k,1,n,1);
129 for(int i=m;i>=1;i--){
130 cin>>p[i].x>>p[i].y>>p[i].v;
131 }
132 for(int i=1;i<=m;i++){
133 addRange(p[i].x,p[i].y,p[i].v);
134 }
135 for(int i=1;i<=n;i++){
136 cout<<ans[i];
137 if(i!=n) cout<<" ";
138 }
139 cout<<endl;
140 }
View Code
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/154528.html原文链接:https://javaforall.cn