雨天的尾巴

[Vani有约会] 雨天的尾巴 /【模板】线段树合并

题目背景

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

题目描述

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 \(n\) 和救济粮发放的次数 \(m\)。

第 \(2\) 到 第 \(n\) 行，每行有两个用空格隔开的整数 \(a, b\)，代表存在一条连接房屋 \(a\) 和 \(b\) 的边。

第 \((n + 1)\) 到第 \((n + m)\) 行，每行有三个用空格隔开的整数 \(x, y, z\)，代表一次救济粮的发放是从 \(x\) 到 \(y\) 路径上的每栋房子发放了一袋 \(z\) 类型的救济粮。

输出格式

输出 \(n\) 行，每行一个整数，第 \(i\) 行的整数代表 \(i\) 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 \(0\)。

样例 #1

样例输入 #1

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

样例输出 #1

2
3
3
0
2

提示

• 对于 \(20\%\) 的数据，保证 \(n, m \leq 100\)。
• 对于 \(50\%\) 的数据，保证 \(n, m \leq 2 \times 10^3\)。
• 对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。

首先连边连成一个树,显然我们需要一个桶,记录pos位置下的值以及其次数,然后我们需要用树上差分以及LCA,

所以可用LCA找到x,y的最近公共祖先以及最近公共祖先的父亲,进行操作,合并过程用线段树合并O(nlogn)的复杂度显然是最优的,关于权值线段树的右边界,注意审题,只需1e5即可

点击查看代码

#include <bits/stdc++.h>
#define lid st[rt].l
#define rid st[rt].r
using namespace std;
int n,m,segtot;
const int N = 1e5+5,MAX=1e5;
vector <int> edge[N];
int root[N],d[N],f[N][33],ans[N];struct tree
{int l,r,cnt,ans,t;
}st[N*80];
int read(){int s=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar()) s=s*10+(ch^48);return s*f;
}
void pushup(int rt)
{if(lid==0){st[rt].cnt=st[rid].cnt;st[rt].t=st[rid].t;	return;}if(rid==0){st[rt].cnt=st[lid].cnt;st[rt].t=st[lid].t;return;		}if(st[lid].cnt>=st[rid].cnt){st[rt].cnt=st[lid].cnt;st[rt].t=st[lid].t;}else{st[rt].cnt=st[rid].cnt;st[rt].t=st[rid].t;		}
}
void dfslca(int x,int fa)
{d[x]=d[fa]+1;f[x][0]=fa;for(int j=1;j<=30;j++){f[x][j]=f[f[x][j-1]][j-1];}
//	cout<<"&&"<<x<<" "<<d[x]<<endl;for(int i=0;i<edge[x].size();i++){int to=edge[x][i];if(to==fa)continue;dfslca(to,x);}
}
void LCA_init()
{
//	for(int j=1;j<=25;j++)
//	{
//		for(int i=1;i<=n;i++)
//		{
//			f[i][j]=f[f[i][j-1]][j-1];
//		}
//	}
}
int lca(int x,int y)
{if(d[x]<d[y])swap(x,y);for(int i=30;i>=0;i--){if(d[f[x][i]]>=d[y])x=f[x][i];}if(x==y)return x;for(int i=30;i>=0;i--){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
int segtree(int ra,int rb,int l,int r)
{if(!ra)return rb;if(!rb)return ra;if(l==r){st[ra].cnt+=st[rb].cnt;return ra;}int mid=(l+r)>>1;st[ra].l=segtree(st[ra].l,st[rb].l,l,mid);st[ra].r=segtree(st[ra].r,st[rb].r,mid+1,r);pushup(ra);	return ra;
}
void update(int &rt,int l,int r,int pos,int val)
{if(!rt)rt=++segtot;if(l==r){st[rt].cnt+=val;st[rt].t=pos;return;}int mid=(l+r)>>1;if(pos<=mid)update(lid,l,mid,pos,val);else update(rid,mid+1,r,pos,val);pushup(rt);
}
//int query(int rt,int l,int r,int L,int R)
//{
//	if(!rt)return 0;
//	
//}
void dfs(int x,int fa)
{for(int i=0;i<edge[x].size();i++){int to=edge[x][i];if(to==fa)continue;dfs(to,x);root[x]=segtree(root[x],root[to],1,MAX);}ans[x]=st[root[x]].t;if(st[root[x]].cnt==0)ans[x]=0;
}
int main()
{
//	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("a.out","r",stdin);cin>>n>>m;int a,b;for(int i=1;i<=n-1;i++){a=read();b=read();
//		cin>>a>>b;edge[a].push_back(b);edge[b].push_back(a);}dfslca(1,0);
//	LCA_init();int x,y,z;for(int i=1;i<=m;i++){x=read();y=read();z=read();
//		cin>>x>>y>>z;int q=lca(x,y);
//		cout<<"###"<<q<<endl;update(root[x],1,MAX,z,1);update(root[y],1,MAX,z,1);update(root[q],1,MAX,z,-1);if(f[q][0])update(root[f[q][0]],1,MAX,z,-1);}dfs(1,0);for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}