清明梦超能力者黄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)
blank

相关推荐

发表回复

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

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