关键词:
题意:给一颗树,n个节点,m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1,最后询问每个节点中数量最多的颜色。
思路:显然,我们得维护每个节点中颜色的最大值。那么我们给每个节点开一颗权值线段树,维护颜数量的最大值。现在关键是如何优化路径操作 —— 树上差分。
关于树上差分的可以参考蓝书上的解释
“根据差分序列的前缀和是原序列"这一原理,在树上可以进行类似的化简,其中"区间操作"对应为"路径操作”,“前缀和"对应为"子树和”。
我们设u,v的lca为t,类似于数列上差分我们让u的z+1, v的z+1, t的z-1,t的父亲-1(存在的话)。现在前缀和的过程就相当于是合并线段树的过程。(这空间消耗也太大了…)
#include<bits/stdc++.h>
using namespace std;
#define endl "\\n"
#define lsn (u << 1)
#define rsn (u << 1 | 1)
#define mid (l + r >> 1)
const int MAXN = 1e5 + 10;
const int MAX_LEN = 1e7;
vector<int> g[MAXN];
int n, m, tot;
int tr[MAX_LEN], cnt[MAX_LEN], ans[MAXN];
int rt[MAX_LEN], ls[MAX_LEN], rs[MAX_LEN];
int dp[21][MAXN], depth[MAXN];
void pushup(int u)
if(cnt[ls[u]] >= cnt[rs[u]]) cnt[u] = cnt[ls[u]]; tr[u] = tr[ls[u]];
else cnt[u] = cnt[rs[u]]; tr[u] = tr[rs[u]];
void upd(int &u, int l, int r, int p, int d)
if(!u) u = ++tot;
if(l == r && l == p)
cnt[u] += d;
tr[u] = p;
else
if(p <= mid) upd(ls[u], l, mid, p, d);
else upd(rs[u], mid+1, r, p, d);
pushup(u);
int merge(int p, int q, int l, int r)
if(!p) return q;
if(!q) return p;
if(l == r)
cnt[p] += cnt[q];
tr[p] = l;
return p;
ls[p] = merge(ls[p], ls[q], l, mid);
rs[p] = merge(rs[p], rs[q], mid+1, r);
pushup(p);
return p;
void dfs1(int u, int p)
depth[u] = depth[p] + 1;
dp[0][u] = p;
for(auto v : g[u])
if(v == p) continue;
dfs1(v, u);
void dfs2(int u, int p)
for(auto v : g[u])
if(v == p) continue;
dfs2(v, u);
rt[u] = merge(rt[u], rt[v], 1, 1e5);
if(cnt[rt[u]]) ans[u] = tr[rt[u]];
int lca(int u, int v)
if(depth[u] < depth[v]) swap(u, v);
for(int i = 0; i <= 20; i++)
if((depth[u]-depth[v]) >> i & 1)
u = dp[i][u];
if(u == v) return v;
for(int i = 20; i >= 0; i--)
if(dp[i][u] != dp[i][v])
u = dp[i][u];
v = dp[i][v];
return dp[0][u];
void solve()
cin >> n >> m;
for(int i = 1; i < n; i++)
int u, v; cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
dfs1(1, 0);
for(int i = 0; i + 1 <= 20; i++)
for(int u = 1; u <= n; u++)
dp[i+1][u] = dp[i][dp[i][u]];
while(m--)
int u, v, x;
cin >> u >> v >> x;
int t = lca(u, v);
upd(rt[u], 1, 1e5, x, 1);
upd(rt[v], 1, 1e5, x, 1);
upd(rt[t], 1, 1e5, x, -1);
if(dp[0][t] != 0) upd(rt[dp[0][t]], 1, 1e5, x, -1);
dfs2(1, 0);
for(int i = 1; i <= n; i++)
cout << ans[i] << endl;
int main()
ios::sync_with_stdio(false);
solve();
return 0;
p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)
传送门题意:给一颗树,n个节点,m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1,最后询问每个节点中数量最多的颜色。思路:显然,我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情
p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)
传送门题意:给一颗树,n个节点,m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1,最后询问每个节点中数量最多的颜色。思路:显然,我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情
p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)
传送门题意:给一颗树,n个节点,m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1,最后询问每个节点中数量最多的颜色。思路:显然,我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情
[vani有约会]雨天的尾巴(代码片段)
我之前考试是遇到过这题,但是数据范围k<=20,状压就能过。结果原题范围k<=100000……果断线段树合并。普及线段树合并:比如两个相同大小的线段树,将b树各个区间上的值合并到a树上,从树根开始合并,然后递归合并左右... 查看详情
bzoj3307雨天的尾巴线段树合并
http://www.elijahqi.win/archives/3463DescriptionN个点,形成一个树状结构。有M次发放,每次选择两个点x,y对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成所有发放后,每个点存放最多的是哪种物品。Input第一行数字N,... 查看详情
bzoj3307雨天的尾巴(可持久化线段树合并)(代码片段)
题目大意:一颗树,想要在树链上添加同一物品,问最后每个点上哪个物品最多。解题思路:假如说物品数量少到可以暴力添加,且树点极少,我们怎么做。首先在一个树节点上标记出哪些物品有多少,寻找道路上的节点暴力添... 查看详情
luogu4556雨天的尾巴树上差分线段树合并(代码片段)
传送门 一个套路题……树上差分+线段树合并即可注意一个细节:$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$,否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码,因为这份代码没有卡空... 查看详情
luogu4556雨天的尾巴(线段树合并+差分)(代码片段)
题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮... 查看详情
bzoj3307雨天的尾巴
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3307【题解】这什么垃圾题啊卡空间卡时间卡栈然后我会了一种新姿势:人工栈(好像也不难啊喂)我们发现对于每种物品,只需要在u这地方的权值线段树上+1,v的权值线段树上+1,LC... 查看详情
bzoj3307雨天的尾巴
题目链接:传送门题目大意:中文题,略题目思路:网上有题解说是合并线段树的,但是太难蒟蒻不会,只能用树剖求解 如果不是树而是一维数组我们会怎么解? 当然是利用前缀和思想标记(... 查看详情
bzoj-3307:雨天的尾巴
咱可以差分一下,把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$,$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询,最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了,$RE$了一次。1#include<cassert>2#inclu... 查看详情
雨天的尾巴(代码片段)
考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程:当时想到了离散化(很慌没打出来。。。),树上差分,lca倍增,当时觉滴倍增很难打,一看n<100000,于是选择用向上标记法,然而少了一行代码,,,,爆... 查看详情
例题线段树合并(代码片段)
雨天的尾巴这道题应该算是很板子了,不过需要稍微思考一下,对于每次发放,如果模拟发放过程,那么每次发放的时间复杂度是(O(n))的,这样显然会T,考虑如果每次只发放一种,用树上差分解决就可以,但是这个有很多种,... 查看详情
[luogu4556]雨天的尾巴(代码片段)
[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情
bzoj3307:雨天的尾巴(代码片段)
传送门树上差分+线段树合并+离散化对于修改的路径,树上差分就好了代码:#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情
线段树合并(代码片段)
3307:雨天的尾巴模板题。简单题调不过最好的方法是重构代码或者放一天然后重构代码。1//Achen2#include<algorithm>3#include<iostream>4#include<cstring>5#include<cstdlib>6#include<vector>7#include<cstdio>8#inc 查看详情
hdu4553约会安排(区间合并)线段树(代码片段)
<题目链接> 寒假来了,又到了小明和女神们约会的季节。 小明虽为屌丝级码农,但非常活跃,女神们常常在小明网上的大段发言后热情回复“呵呵”,所以,小明的最爱就是和女神们约会。与此同时,也有很多... 查看详情
hdu4553约会安排(线段树区间合并+双重标记)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4553题目大意:就是有三种操作: ①DS x,安排一段长度为x的空闲时间跟屌丝一起,输出这段时间的起点,若没有则输出“flywithyourself”。 ②NS x,安... 查看详情