关键词：
我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。
结果原题范围k<=100000……
果断线段树合并。
普及线段树合并：
比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右儿子，有三种情况：
（假设现在a树遍历到x点，b树遍历到y点）
1.x，y至少其一未被修改过（语文不好勿喷），则将x变为遍历过的那个。
2.x，y位于叶节点（l==r），则sum[x]+=sum[y]。
3.一般情况，递归处理左右儿子，最后更新当前点。
本题中合并如下：
void merge(int &a,int b,int l,int r)
if(!b)return ;
if(!a)a=b;return ;
//1
if(l==r)sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;//注意维护
//2
int mid = (l+r)>>1;
merge(ls[a],ls[b],l,mid);//递归左子树
merge(rs[a],rs[b],mid+1,r);//递归右子树
update(a);
//3
juruo代码奉上：
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100105
inline int rd()
int f=1,c=0;char ch = getchar();
while(ch<‘0‘||ch>‘9‘)if(ch==‘-‘)f=-1;ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)c=10*c+ch-‘0‘;ch=getchar();
return f*c;
int n,m,hed[N],cnt;
struct eg
int to;
int nxt;
e[2*N];
void ae(int f,int t)
e[++cnt].to = t;
e[cnt].nxt = hed[f];
hed[f] = cnt;
int dep[N],fa[N],son[N],tp[N],siz[N];
void dfs1(int u)
dep[u]=dep[fa[u]]+1;
siz[u]=1;
for(int j=hed[u];j;j=e[j].nxt)
int to = e[j].to;
if(to==fa[u])continue;
fa[to]=u;
dfs1(to);
siz[u]+=siz[to];
if(siz[to]>siz[son[u]])son[u]=to;
void dfs2(int u,int topn)
tp[u]=topn;
if(!son[u])return ;
dfs2(son[u],topn);
for(int j=hed[u];j;j=e[j].nxt)
int to = e[j].to;
if(to==fa[u]||to==son[u])continue;
dfs2(to,to);
int get_lca(int a,int b)
while(tp[a]!=tp[b])
if(dep[tp[a]]<dep[tp[b]])swap(a,b);
a=fa[tp[a]];
return dep[a]<dep[b]?a:b;
int rt[N],sum[70*N],sn[70*N],ls[70*N],rs[70*N],tot;
void update(int u)
sn[u]=sum[ls[u]]>=sum[rs[u]]?sn[ls[u]]:sn[rs[u]];
sum[u]=sum[ls[u]]>=sum[rs[u]]?sum[ls[u]]:sum[rs[u]];
void insert(int l,int r,int &u,int qx,int d)
if(!u)u=++tot;
if(l==r)
sum[u]+=d;
if(sum[u])sn[u]=l;
else sn[u]=0;
return ;
int mid = (l+r)>>1;
if(qx<=mid)insert(l,mid,ls[u],qx,d);
else insert(mid+1,r,rs[u],qx,d);
update(u);
void merge(int &a,int b,int l,int r)
if(!b)return ;
if(!a)a=b;return ;
if(l==r)sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;
int mid = (l+r)>>1;
merge(ls[a],ls[b],l,mid);
merge(rs[a],rs[b],mid+1,r);
update(a);
int ans[N];
void dfs(int u)
for(int j=hed[u];j;j=e[j].nxt)
int to = e[j].to;
if(to==fa[u])continue;
dfs(to);
merge(rt[u],rt[to],1,m);
ans[u]=sn[rt[u]];
struct ND
int f,t,z;
nd[N];
bool cmp(ND a,ND b)
return a.z<b.z;
int to[N];
int main()
n=rd(),m=rd();
for(int f,t,i=1;i<n;i++)
f=rd(),t=rd();
ae(f,t),ae(t,f);
dfs1(1),dfs2(1,1);
for(int f,t,z,i=1;i<=m;i++)
f=rd(),t=rd(),z=rd();
nd[i].f=f,nd[i].t=t,nd[i].z=z;
sort(nd+1,nd+1+m,cmp);
int las=-1,k=0;
for(int f,t,z,lca,i=1;i<=m;i++)
if(nd[i].z!=las)
las=nd[i].z;
to[++k]=nd[i].z;
nd[i].z=k;
f = nd[i].f,t = nd[i].t,z = nd[i].z;
lca = get_lca(f,t);
insert(1,m,rt[f],z,1);
insert(1,m,rt[t],z,1);
insert(1,m,rt[lca],z,-1);
if(lca!=1)insert(1,m,rt[fa[lca]],z,-1);
dfs(1);
for(int i=1;i<=n;i++)
printf("%d
",to[ans[i]]);
return 0;
在这里提一下空间问题：
每进行一次插入，会添加log级的点，因此juruo认为开nlogn级数组即可。
权值线段树-动态开点-合并（p4556[vani有约会]雨天的尾巴(代码片段)
题意：https://www.luogu.com.cn/problem/P4556树链加数，问你每个节点最多的是哪个数。思路：树链加数很容易想到差分。从下往上用权值线段树合并即可，直接用pushup把答案存在树根即可，不用每次查询最多的数1structEDGE23intto,next;4edge[N... 查看详情
p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)
传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情
p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)
传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情
p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)
传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情
雨天的尾巴(代码片段)
考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程：当时想到了离散化（很慌没打出来。。。），树上差分，lca倍增，当时觉滴倍增很难打，一看n<100000,于是选择用向上标记法，然而少了一行代码，，，，爆... 查看详情
[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) 查看详情
gdoi2014模拟雨天的尾巴(代码片段)
题目深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被... 查看详情
bzoj3307雨天的尾巴（可持久化线段树合并）(代码片段)
题目大意：一颗树，想要在树链上添加同一物品，问最后每个点上哪个物品最多。解题思路：假如说物品数量少到可以暴力添加，且树点极少，我们怎么做。首先在一个树节点上标记出哪些物品有多少，寻找道路上的节点暴力添... 查看详情
luogu4556雨天的尾巴树上差分线段树合并(代码片段)
传送门 一个套路题……树上差分+线段树合并即可注意一个细节：$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$，否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码，因为这份代码没有卡空... 查看详情
luogu4556雨天的尾巴(线段树合并+差分)(代码片段)
题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮... 查看详情
[bzoj3307]雨天的尾巴(代码片段)
DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，M接下来N-1行，每行两个数字a,b,表示a与b... 查看详情
bzoj3307:雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 479 Solved: 214[Submit][Status][Discuss]DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的 查看详情
[bzoj3307]雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 709 Solved: 296[Submit][Status][Discuss]DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的 查看详情
bzoj3307雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBDescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。... 查看详情
bzoj3307雨天的尾巴
题目链接：传送门题目大意：中文题，略题目思路：网上有题解说是合并线段树的，但是太难蒟蒻不会，只能用树剖求解 如果不是树而是一维数组我们会怎么解？ 当然是利用前缀和思想标记（... 查看详情
bzoj3307雨天的尾巴线段树合并
http://www.elijahqi.win/archives/3463DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，... 查看详情
gdoi模拟雨天的尾巴树套树
雨天的尾巴深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的... 查看详情