正文 

当前位置： 首页 > 代码 > java教程

bzoj3307:雨天的尾巴(代码片段)

lcxer lcxer     2022-12-03     480

关键词：

传送门

树上差分+线段树合并+离散化
对于修改的路径，树上差分就好了
代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<tr1/unordered_map>
#include<algorithm>
using namespace std;
void read(int &x) 
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

#define rg register
const int maxn=1e5+10;
int dep[maxn],n,m,id,tot,pre[maxn*2],rt[maxn],ls[maxn*50],f[maxn][20],x[maxn],y[maxn],z[maxn],nid[maxn];
int rs[maxn*50],mx[maxn*50],mxid[maxn*50],nxt[maxn*2],h[maxn],cnt,ans[maxn],w[maxn];tr1::unordered_map<int,int>mp;
bool vis[maxn];
void add(int x,int y)

    pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt;
    pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt;

void dfs(int x,int fa)

    for(rg int i=1;i<20;i++)
    
        if((1<<i)>dep[x])break;
        f[x][i]=f[f[x][i-1]][i-1];
    
    for(rg int i=h[x];i;i=nxt[i])
        if(pre[i]!=fa)f[pre[i]][0]=x,dep[pre[i]]=dep[x]+1,dfs(pre[i],x);

int lca(int x,int y)

    if(dep[x]>dep[y])swap(x,y);
    int poor=dep[y]-dep[x];
    for(rg int i=19;i>=0;i--)if(poor&(1<<i))y=f[y][i];
    if(x==y)return x;
    for(rg int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return x==y?x:f[x][0];

void update(int x)

    if(mx[ls[x]]>mx[rs[x]]||(mx[ls[x]]==mx[rs[x]]&&mxid[ls[x]]<mxid[rs[x]]))mx[x]=mx[ls[x]],mxid[x]=mxid[ls[x]];
    else if(mx[ls[x]]<mx[rs[x]]||(mx[ls[x]]==mx[rs[x]]&&mxid[ls[x]]>mxid[rs[x]]))mx[x]=mx[rs[x]],mxid[x]=mxid[rs[x]];

void change(int &k,int l,int r,int a,int b)

    if(!k)k=++id;int mid=(l+r)>>1;
    if(l==r)mx[k]+=b,mxid[k]=l;return ;
    if(a<=mid)change(ls[k],l,mid,a,b);
    else change(rs[k],mid+1,r,a,b);
    update(k);

int merge(int x,int y,int l,int r)

    if(!x||!y)return x+y;
    int mid=(l+r)>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    if(l==r)mx[x]+=mx[y];else update(x);
    return x;

void solve(int x,int fa)

    for(rg int i=h[x];i;i=nxt[i])
        if(pre[i]!=fa)
        
            solve(pre[i],x);
            rt[x]=merge(rt[x],rt[pre[i]],1,tot);
        
    ans[x]=nid[mxid[rt[x]]];

int main()

    read(n),read(m);
    for(rg int i=1,x,y;i<n;i++)read(x),read(y),add(x,y);
    dfs(1,0);
    for(rg int i=1;i<=m;i++)read(x[i]),read(y[i]),read(z[i]),w[i]=z[i];
    sort(w+1,w+m+1);tot=0;
    for(rg int i=1;i<=m;i++)if(w[i]!=w[i-1])mp[w[i]]=++tot,nid[tot]=w[i];
    for(rg int i=1;i<=m;i++)
    
        int fa=lca(x[i],y[i]);
        change(rt[x[i]],1,tot,mp[z[i]],1),change(rt[y[i]],1,tot,mp[z[i]],1),
        change(rt[fa],1,tot,mp[z[i]],-1),change(rt[f[fa][0]],1,tot,mp[z[i]],-1);
    
    solve(1,0);
    for(rg int i=1;i<=n;i++)printf("%d\n",ans[i]);

[bzoj3307]雨天的尾巴

3307:雨天的尾巴TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 709  Solved: 296[Submit][Status][Discuss]DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的 查看详情

bzoj3307雨天的尾巴（可持久化线段树合并）(代码片段)

题目大意：一颗树，想要在树链上添加同一物品，问最后每个点上哪个物品最多。解题思路：假如说物品数量少到可以暴力添加，且树点极少，我们怎么做。首先在一个树节点上标记出哪些物品有多少，寻找道路上的节点暴力添... 查看详情

bzoj3307雨天的尾巴

3307:雨天的尾巴TimeLimit: 10Sec  MemoryLimit: 128MBDescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。... 查看详情

bzoj3307雨天的尾巴

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3307【题解】这什么垃圾题啊卡空间卡时间卡栈然后我会了一种新姿势：人工栈（好像也不难啊喂）我们发现对于每种物品，只需要在u这地方的权值线段树上+1，v的权值线段树上+1，LC... 查看详情

bzoj-3307:雨天的尾巴

咱可以差分一下，把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$，$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询，最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了，$RE$了一次。1#include<cassert>2#inclu... 查看详情

bzoj3307雨天的尾巴

题目链接：传送门题目大意：中文题，略题目思路：网上有题解说是合并线段树的，但是太难蒟蒻不会，只能用树剖求解　　　　　如果不是树而是一维数组我们会怎么解？   　　　　　当然是利用前缀和思想标记（... 查看详情

[bzoj3307]雨天的尾巴(代码片段)

DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，M接下来N-1行，每行两个数字a,b,表示a与b... 查看详情

bzoj3307雨天的尾巴线段树合并

​​http://www.elijahqi.win/archives/3463​​​DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，... 查看详情

考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)

...来想用哈希只可以得20左右没想到由于数据过于水A了然后雨天的尾巴骗了5分，总分105我太菜了首先时间分配的不合理：第一题大水题ac自动机打完了都不会，第二题略微想了想打了个高斯消元，然后样例没过......，最后输出了一... 查看详情

[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 查看详情

雨天的尾巴(代码片段)

考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程：当时想到了离散化（很慌没打出来。。。），树上差分，lca倍增，当时觉滴倍增很难打，一看n<100000,于是选择用向上标记法，然而少了一行代码，，，，爆... 查看详情

gdoi2014模拟雨天的尾巴(代码片段)

题目深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被... 查看详情

luogu4556雨天的尾巴树上差分线段树合并(代码片段)

传送门 一个套路题……树上差分+线段树合并即可注意一个细节：$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$，否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码，因为这份代码没有卡空... 查看详情

[vani有约会]雨天的尾巴(代码片段)

我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。结果原题范围k<=100000……果断线段树合并。普及线段树合并：比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右... 查看详情

luogu4556雨天的尾巴(线段树合并+差分)(代码片段)

题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮... 查看详情

p4556[vani有约会]雨天的尾巴（线段树合并）(代码片段)

传送门一道线段树合并首先不难看出树上差分我们把每一次修改拆成四个，在(u,v)分别放上一个，在(lca)和(fa[lca])各减去一个，那么只要统计一下子树里的总数即可然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段... 查看详情

权值线段树-动态开点-合并（p4556[vani有约会]雨天的尾巴(代码片段)

题意：https://www.luogu.com.cn/problem/P4556树链加数，问你每个节点最多的是哪个数。思路：树链加数很容易想到差分。从下往上用权值线段树合并即可，直接用pushup把答案存在树根即可，不用每次查询最多的数1structEDGE23intto,next;4edge[N... 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情