大家好，又见面了，我是你们的朋友全栈君。
清明梦超能力者黄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吧！
又是一个晚上，黄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.net/154528.html原文链接：https://javaforall.net
