清明梦超能力者黄YY(idx数组)

清明梦超能力者黄YY(idx数组)清明梦超能力者黄YYhttps://www.nowcoder.com/acm/contest/206/I题目描述黄YY是一个清明梦超能力者,同时也是一个记忆大师。他能够轻松控制自己在梦中的一切,

大家好,又见面了,我是你们的朋友全栈君。

清明梦超能力者黄YY

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数组标记线段树的某个位置是对应原来数组的哪个位置

<span role="heading" aria-level="2">清明梦超能力者黄YY(idx数组)
<span role="heading" aria-level="2">清明梦超能力者黄YY(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

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/154528.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ActiveMQ入门系列三:发布/订阅模式

    在上一篇《ActiveMQ入门系列二:入门代码实例(点对点模式)》中提到了ActiveMQ中的两种模式:点对点模式(PTP)和发布/订阅模式(Pub&Sub),详细介绍了点对点模式并用代码

  • FT到底值多少钱——再议Fcoin机制及估值模型[通俗易懂]

    一、写在前面两星期前,「朋克」写了一篇关于Fcoin的文章——《FcoinToken(FT)——数字货币交易所的颠覆者,还是无情镰刀的收割者》,彼时全网整体舆论偏负面,称FT为“资金盘”、“传销币”、“庞氏骗局”屡屡不绝。当时「朋克」整体对FT做了较为客观的中性偏正面评价。 仅仅一个星期之后,随着张健的“以德报怨”,在Fcoin上线bnb之后,舆论迅速反转,整体舆论从负面慢慢变…

  • 权重系数确定问题_如何确定权重系数例子

    权重系数确定问题_如何确定权重系数例子根据各个指标获得综合指标时,由于各个指标对综合指标的贡献度不同,相应权重也应不同,对综合指标贡献大的指标更重要,应该分配更大的权重。如何确定各个指标的权重,这里介绍两种方法:熵值法和pca确定权重。也

  • 怎么创建css样式表,怎样创建可反复使用的外部CSS样式表?[通俗易懂]

    怎么创建css样式表,怎样创建可反复使用的外部CSS样式表?[通俗易懂]创建可反复使用的外部CSS样式表用DreamWeaver在某网页中创建了一种CSS样式后,如果你要在另外的网页中应用该样式,你不必从新创建该CSS样式,只要你创建了外部CSS样式表文件(externalCSSstylesheet),你便可以在今后任意调用该样式表文件中的样式。为了便于管理,先在站点所在文件夹中,新建一个文件夹,取名为CSS,专门用于放置外部样式表文件(其扩展名为css)。1、在Do…

  • 如何免费申请博客 用WordPress建设网站

    如何免费申请博客 用WordPress建设网站如何用WordPress搭建博客  10年前左右开始兴起第一波互联网浪潮,博客作为一种新型的社交和阅读方式进入人们的视野,那一段时期是博客的黄金时代。现在,人们说“博客已死”。因为大概在7、8年前第二波互联网浪潮突然出现,且来势汹汹——移动互联网的时代到来了。人们被各种新型的社交媒体所吸引,单单手机APP就使人们忙的目不暇接。人们的选择越来越多,于是碎片化的娱乐逐渐成为人们社交休闲方式。人们不…

  • 在linux中使用md5校验文件的完整性

    在linux中使用md5校验文件的完整性

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号