关键词：

[luogu4556]雨天的尾巴

luogu
发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并
但是...
如果你只有35分...
https://www.luogu.org/discuss/show/88259

#include<bits/stdc++.h>
using namespace std;
const int _=1e5+5;
int re()
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9')if(ch=='-')w=-1;ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;

int n,m,cnt,N=1e5,tot;
int h[_],f[_],a[_],b[_],z[_],fa[_],lca[_],rt[_],ans[_];
int mx[_*67],id[_*67],ls[_*67],rs[_*67];
bool vis[_];
vector<int>p[_];
struct edgeint to,next;e[_<<1];
void link(int u,int v)
    e[++cnt]=(edge)v,h[u];h[u]=cnt;
    e[++cnt]=(edge)u,h[v];h[v]=cnt;

int find(int x)return x==f[x]?x:f[x]=find(f[x]);
void dfs(int u)
    for(int i=h[u];i;i=e[i].next)
        int v=e[i].to;
        if(v==fa[u])continue;
        fa[v]=u;dfs(v);f[v]=u;
    
    vis[u]=1;
    for(int i=0,j=p[u].size();i<j;i++)
        int k=p[u][i],v=a[k]==u?b[k]:a[k];
        if(vis[v])lca[k]=find(v);
    

void pu(int x)
    mx[x]=max(mx[ls[x]],mx[rs[x]]);
    if(mx[ls[x]]==mx[rs[x]])id[x]=min(id[ls[x]],id[rs[x]]);
    else id[x]=mx[ls[x]]>mx[rs[x]]?id[ls[x]]:id[rs[x]];

void upd(int&x,int l,int r,int k,int v)
    if(!x)x=++tot;
    if(l==r)mx[x]+=v;id[x]=l;return;
    int mid=(l+r)>>1;
    if(k<=mid)upd(ls[x],l,mid,k,v);
    else upd(rs[x],mid+1,r,k,v);pu(x);

int merge(int a,int b,int l,int r)
    if(!a||!b)return a|b;
    if(l==r)mx[a]+=mx[b];
    else
        int mid=(l+r)>>1;
        ls[a]=merge(ls[a],ls[b],l,mid);
        rs[a]=merge(rs[a],rs[b],mid+1,r);
        pu(a);
    return a;

void solve(int u)
    for(int i=h[u];i;i=e[i].next)
        int v=e[i].to;
        if(v==fa[u])continue;
        solve(v);
        rt[u]=merge(rt[u],rt[v],1,N);
    
    ans[u]=id[rt[u]];

int main()
    n=re();m=re();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,u,v;i<n;i++)
        u=re(),v=re();link(u,v);
    
    for(int i=1;i<=m;i++)
        a[i]=re(),b[i]=re();z[i]=re();
        p[a[i]].push_back(i);
        p[b[i]].push_back(i);
    
    dfs(1);
    for(int i=1;i<=m;i++)
        upd(rt[a[i]],1,N,z[i],1);
        upd(rt[b[i]],1,N,z[i],1);
        upd(rt[lca[i]],1,N,z[i],-1);
        upd(rt[fa[lca[i]]],1,N,z[i],-1);
    
    solve(1);
    for(int i=1;i<=n;i++)printf("%d
",ans[i]);
    return 0;

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

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

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

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

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

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

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

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

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

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

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

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

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

传送门树上差分+线段树合并+离散化对于修改的路径，树上差分就好了代码：#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情

雨天的尾巴(代码片段)

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

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

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

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

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

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

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

[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类型的物品。完成所有发放后，每个点存放最多的是哪种物品。... 查看详情

gdoi模拟雨天的尾巴树套树

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

gdoi模拟雨天的尾巴树套树

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

bzoj-3307:雨天的尾巴

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