Eternity

Until The End

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

发表于 更新于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

“炽焰卷天，在本就无望的未来上，灼烧出笼罩黑暗的深洞。”

题意

给定一棵 $n$ 个结点的树，每次在路径 $(u,v)$ 添上一种颜色 $c$ ，询问每一个结点颜色数量最多的颜色。

$n\leq 10^5$ 。

题解

树链剖分 x 树上差分

能想到，对于这种统计众值的 $\text{DS}$ 题并不好直接修改路径，所以考虑树上差分，把修改路径变成修改点，然后统计差分。那么，很容易想到，在 $(u,v)$ 上添加 $c$ 颜色，实质上就是在 $u$ 结点加上 $c$ ，$v$ 结点加上 $c$ ，$lca(u,v)$ 减去 $c$ ，$fa_{lca(u,v)}$ 减去 $c$ 。

这个差分的结论在树剖和线段树合并都是必须的。

然后考虑如何用树剖来维护。

因为是离线的查询，只有最后一次查询，所以可以考虑把所有修改放在一起用。

然后建立一棵值域线段树，并维护区间众值。最后按照 $dfn$ 序统一修改，即可统计差分前缀和，我们需要的答案就是 $Tr[1].ans$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
const int MAXN=1e5+10;
int N,Q;
struct TC
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(TC){Head[u],v};Head[u]=Total;
    Edge[++Total]=(TC){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Siz[MAXN],Dep[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Siz[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN],Dfn[MAXN],Bck[MAXN],Cnt;
void dfsChain(int x,int topf)
{
    Top[x]=topf,Dfn[x]=++Cnt;
    Bck[Cnt]=x;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
#define ls p<<1
#define rs p<<1|1
struct ST
{
    int l,r,val,ans;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
    Tr[p].val=std::max(Tr[ls].val,Tr[rs].val);
    if(Tr[p].val==Tr[ls].val) Tr[p].ans=Tr[ls].ans;
    else Tr[p].ans=Tr[rs].ans;
}
void build(int p,int l,int r)
{
    Tr[p]=(ST){l,r,0,0};
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
void modifyCol(int p,int x,int c)
{
    if(Tr[p].l==Tr[p].r)
    {
        Tr[p].val+=c;
        Tr[p].val?Tr[p].ans=x:Tr[p].ans=0;
        return ;
    }
    int mid=(Tr[p].l+Tr[p].r)>>1;
    if(x<=mid) modifyCol(ls,x,c);
    else modifyCol(rs,x,c);
    pushUp(p);
}
std::vector<std::pair<int,int>>Modi[MAXN];
inline void modifyDiff(int x,int y,int c)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        Modi[Dfn[Top[x]]].push_back({c,1});
        Modi[Dfn[x]+1].push_back({c,-1});
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) std::swap(x,y);
    Modi[Dfn[x]].push_back({c,1});
    Modi[Dfn[y]+1].push_back({c,-1});
}
int ans[MAXN];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,Q);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
    }
    dfsTree(1,0),dfsChain(1,1);
    build(1,1,MAXN-10);
    for(int u,v,c;Q--;)
    {
        read(u,v,c);modifyDiff(u,v,c);
    }
    for(int i=1;i<=N;++i)
    {
        int sz=Modi[i].size();
        for(int j=0;j<sz;++j) modifyCol(1,Modi[i][j].first,Modi[i][j].second);
        ans[Bck[i]]=Tr[1].ans;
    }
    for(int i=1;i<=N;++i) write(ans[i],'\n');
    return 0;
}
/*
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
*/

线段树合并 x 树上差分

毕竟是模板题。

考虑转换成有根树，对于每一个结点都建立一棵动态开点线段树，然后存储当前结点的答案，并从下至上合并即可。

然后你会发现，线段树合并的口胡都非常的轻松，但是用代码实现起来，需要熟练掌握模板，然后稍稍变换一点，其实也没有多么难写。（然后就写挂了，不太能理解 merge 函数明明很短每次都能把要么 p1,p2 搞混要么 lc,rc 搞混，还是需要提高码力啊）

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
const int MAXN=1e5+10;
int N,Q,Idx,MaxCol;
struct ST
{
    int lc,rc,val,cnt;
}Tr[MAXN*100];
inline void extend(int p1,int p2)
{
    Tr[p1].val=Tr[p2].val,Tr[p1].cnt=Tr[p2].cnt;
}
inline void pushUp(int p)
{
    if(Tr[Tr[p].lc].cnt>Tr[Tr[p].rc].cnt) extend(p,Tr[p].lc);
    else if(Tr[Tr[p].lc].cnt<Tr[Tr[p].rc].cnt) extend(p,Tr[p].rc);
    else if(Tr[Tr[p].lc].val<Tr[Tr[p].rc].val) extend(p,Tr[p].lc);
    else extend(p,Tr[p].rc);
}
void modifyX(int &p,int c,int v,int l,int r)
{
    if(!p) p=++Idx;
    if(l==r)
    {
        Tr[p].cnt+=v,Tr[p].val=c;
        return ;
    }
    int mid=(l+r)>>1;
    if(c<=mid) modifyX(Tr[p].lc,c,v,l,mid);
    else modifyX(Tr[p].rc,c,v,mid+1,r);
    pushUp(p);
}
int merge(int p1,int p2,int l,int r)
{
    if(!p1) return p2;
    if(!p2) return p1;
    if(l==r)
    {
        Tr[p1].cnt+=Tr[p2].cnt;
        return p1;
    }
    int mid=(l+r)>>1;
    Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),
    Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    pushUp(p1);
    return p1;
}
struct G
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Siz[MAXN],Dep[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN],ans[MAXN],Rt[MAXN];
void dfsChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    return Dep[x]>Dep[y]?y:x;
}
std::vector<std::pair<int,int>>Modify[MAXN];
void reDfs(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        reDfs(v,x);
        Rt[x]=merge(Rt[x],Rt[v],0,MaxCol);
    }
    for(auto i:Modify[x]) modifyX(Rt[x],i.first,i.second,0,MaxCol);
    ans[x]=Tr[Rt[x]].val;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,Q);Rt[1]=1,Idx=N;
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
        Rt[i]=i;
    }
    dfsTree(1,0),dfsChain(1,1);
    for(int u,v,c;Q--;)
    {
        read(u,v,c);checkMax(MaxCol,c);
        int o=getLca(u,v);
        Modify[u].push_back({c,1}),Modify[v].push_back({c,1});
        Modify[o].push_back({c,-1}),Modify[Fa[o]].push_back({c,-1});
    }
    reDfs(1,-1);
    for(int i=1;i<=N;++i) write(ans[i],'\n');
    return 0;
}
/*
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
*/
相关文章