bzoj 5457 城市
2024-08-26 17:44:59
题目大意:
树上每个点有种类$a_i$和数量$b_i$,求每个点的子树内数量最多的种类的数量和这个数量
思路:
显然是线段树合并裸题
学习一下$dsu \space on \space tree$ 主要就是保留重链信息 其余点暴力
多用几个函数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define inf 2139062143
#define MAXN 400100
#define MOD 998244353
#define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
#define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
#define ren for(register int i=fst[x];i;i=nxt[i])
#define pb(i,x) vec[i].push_back(x)
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,fst[MAXN],nxt[MAXN<<],to[MAXN<<],t[MAXN],val[MAXN];
int sz[MAXN],hvs[MAXN],cnt,num[MAXN],ans[MAXN],res[MAXN],tmp;
void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
void dfs(int x,int pa)
{
sz[x]=;ren if(to[i]^pa)
{
dfs(to[i],x),sz[x]+=sz[to[i]];
if(sz[to[i]]>sz[hvs[x]]) hvs[x]=to[i];
}
}
void cheq(int &x,int y) {x=(num[y]>num[x]||(num[x]==num[y]&&y<x))?y:x;}
void Get(int x,int pa,int v)
{
num[t[x]]+=v*val[x];if(v>) cheq(tmp,t[x]);
ren if(to[i]^pa) Get(to[i],x,v);
}
void dsu(int x,int pa,int v)
{
ren if(to[i]^pa&&to[i]^hvs[x]) dsu(to[i],x,);
if(hvs[x]) dsu(hvs[x],x,);
ren if(to[i]^pa&&to[i]^hvs[x]) Get(to[i],x,);
num[t[x]]+=val[x];cheq(tmp,t[x]);ans[x]=tmp,res[x]=num[tmp];
if(!v) tmp=,Get(x,pa,-);
}
int main()
{
n=read(),m=read();int a,b;rep(i,,n) a=read(),b=read(),add(a,b),add(b,a);
rep(i,,n) t[i]=read(),val[i]=read();
dfs(,);dsu(,,);rep(i,,n) printf("%d %d\n",ans[i],res[i]);
}
最新文章
- C#对WebApi数据操作
- ECMAScript 5中属性的特性值
- asp.net DataTable 修改列值
- Android基于XMPP的即时通讯2-文件传输
- 初学java之面板布局的控制
- (转载)OC学习篇之---Foundation框架中的NSArray类和NSMutableArray类
- Java的“影子克隆”和“深度克隆”
- 父子页面(iframe)相互获取对方dom元素
- ubuntu下安装pandas出现 compile failed with error code 1 in /tmp/pip_build_hadoop/pandas
- 转:Flutter动画一
- @media screen and (max-width: 960px)与@media (max-width: 960px) 有screen与没有screen的区别
- 2018.3,GC可控了
- 【docker】 VI/VIM 无法使用系统剪贴板(clipboard)
- springMVC参数绑定JSON类型的数据
- 中小型研发团队架构实践五:Redis快速入门及应用
- STL set集合用法总结(multiset)
- Katalon 学习笔记(一)
- C# 接口(3)
- Windows命令行乱码问题解决
- npm package管理