P4556 [Vani有约会]雨天的尾巴

这一题真是什么做法都有啊...

首先看完题目就知道要离线，然后树上差分十分显然

所以现在的问题就是求每个节点子树内出现最多的颜色

这个显然可以每个节点维护一个动态开点权值线段树然后通过儿子节点线段树合并得到当前节点的答案

这个时间复杂度经过分析是 $O(n log ^2n)$，因为每个插入多 $log n$ 个节点，总节点数就是 $n log n$，然后线段树合并的时候线段树上每有一个满足条件的 $lca$ 就合并两个节点，合并次数和点数是同阶的，而枚举到 $lca$ 时的时间复杂度就是线段树上 $lca$ 的深度，深度是也是 $log$ 的

所以最后时间复杂度就是 $O(n log ^2n)$，然后空间显然是和时间同阶的，但是注意我们因为树上差分所以空间要多 $4$ 倍

或者怕被卡空间也可以用平衡树启发式合并代替线段树合并，显然平衡树点数就是询问数，然后启发式合并就是一个 $log$

总复杂度也是 $O(n log ^2n)$

然后这两种做法我都不想写，我去看了另外两种做法

$dsu on tree$ 和 $set+map$

$dsu on tree$ 时动态维护当前的答案，维护 $cnt[i]$ 表示颜色 $i$ 的出现次数，开 $m$ 个 $set$ $S[]$，$S[i]$ 表示出现次数为 $i$ 的各个颜色编号，顺便维护一下当前的最大出现次数 $mx$

那么因为每次修改颜色出现次数时就修改 $cnt$，然后从原 $cnt$ 的 $S[cnt]$ 中删除这个颜色然后在新的 $cnt$ 的 $S[cnt]$ 中插入这个颜色，同时判断 $mx$ 是否要改变，因为每次修改都为 $1$ ，所以 $mx$ 每次也只要考虑加减 $1$

然后 $dsu on tree$ 复杂度 $n log n$， $set$ 单次复杂度 $log n$，总复杂度也是 $O(n log ^2n)$

还有一种做法 $set+map$，因为如果直接用 $set$ 维护双关键字：出现次数，颜色，因为我们排序是按出现次数为第一关键字的，只能知道出现次数最多的颜色是什么，如果我们想修改这种颜色的出现次数如果只是根据颜色这个信息没法快速定位

考虑多维护一个 $map$ ，$map[x]$ 的值就表示颜色 $x$ 的出现次数，那么要修改的时候我们只要根据 $map$ 里的出现次数配合颜色来定位 $set$ 里的这个元素位置即可

然后用上启发式合并复杂度也是 $O(n log ^2n)$

代码里用的是最后一种方法，$STL$ 大法好，最后，因为人傻常数大所以请配合 $O2$ 食用

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e5+7;
int n,m,ans[N];
int fir[N],from[N<<1],to[N<<1],cntt;
inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; }
struct dat {
    int c,v;
    dat (int _c=0,int _v=0) { c=_c,v=_v; }
    inline bool operator < (const dat &tmp) const {
        return v!=tmp.v ? v>tmp.v : c<tmp.c;
    }
    inline dat operator + (const dat &tmp) const {
        return dat(c,v+tmp.v);
    }
};
set <dat> S[N];
set <dat>::iterator it;
map <int,int> mp[N];
vector <dat> V[N];
inline void merge(int u,int v)
{
    if(S[u].size()<S[v].size()) swap(S[u],S[v]),swap(mp[u],mp[v]);
    for(auto x: S[v])
    {
        it=S[u].find(dat(x.c,mp[u][x.c]));
        if(it==S[u].end()) mp[u][x.c]=x.v,S[u].insert(x);
        else
        {
            dat p=*it; S[u].erase(p);
            mp[u][x.c]+=x.v; if(mp[u][x.c]) S[u].insert(p+x);//注意这里出现次数不为0才加入set!
        }
    }
}
void dfs(int x,int fa)
{
    for(int i=fir[x];i;i=from[i])
    {
        int &v=to[i]; if(v==fa) continue;
        dfs(v,x); merge(x,v);
    }
    for(auto A: V[x])
    {
        it=S[x].find(dat(A.c,mp[x][A.c]));
        if(it==S[x].end())
        {
            S[x].insert(dat(A.c,A.v)); mp[x][A.c]=A.v;
            continue;
        }
        dat p=*it; S[x].erase(p);
        mp[x][A.c]+=A.v; if(mp[x][A.c]) S[x].insert(p+A);//注意这里出现次数不为0才加入set!
    }
    ans[x]=S[x].size() ? (*S[x].begin()).c : 0;//记得特判空集
}
int f[N][21],dep[N];
void pre_dfs(int x)
{
    dep[x]=dep[f[x][0]]+1;
    for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=fir[x];i;i=from[i])
    {
        int &v=to[i]; if(v==f[x][0]) continue;
        f[v][0]=x; pre_dfs(v);
    }
}
inline int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    n=read(),m=read(); int a,b,c;
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        add(a,b),add(b,a);
    }
    pre_dfs(1);
    for(int i=1;i<=m;i++)
    {
        a=read(),b=read(),c=read(); int lca=LCA(a,b);
        V[a].push_back(dat(c,1)); V[b].push_back(dat(c,1));
        V[lca].push_back(dat(c,-1)); V[f[lca][0]].push_back(dat(c,-1));
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%d
",ans[i]);
    return 0;
}

P4556 [Vani有约会]雨天的尾巴

相关推荐