抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

U81395 换根の树

发布于：2019年8月4日

首先，乖♂乖♂交♂出数据生成器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
inline int gen(){
    return (rand()<<15)|(rand());
}
int main(){
    srand(time(NULL));
    int n=1000,m=1000;
    printf("%d %d\n",n,m);
    for (register int i=1;i<=n;++i){
        printf("%d ",gen()%10+1);
    }
    printf("\n");
    for (register int i=2;i<=n;++i){
        printf("%d %d\n",i,gen()%(i-1)+1);
    }
    printf("\n");
    for (register int i=1;i<=m;++i){
        int opr=(rand()%10==0)?1:2;
        printf("%d %d\n",opr,gen()%n+1);
    }
}

使用printf("%d ",gen()%10+1);是因为如果val[i]val[i]的范围太大，数据基本上全是00。

所以这题的数据范围是假的，当然最后一个点是真·数据范围。

为什么int opr=(rand()%10==0)?1:2;呢？，是因为换♂根太多也不好啊。

30pts30pts

真·大暴力，每次求出颜色总数，根据组合数算一下就可以了：

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
int col[MAXN];
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^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int nowu;
int val[MAXN];
void dfs(int u,int father,bool in){
    if (u==nowu) in=true;
    if (in) col[val[u]]++;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father){
            dfs(v,u,in);
        }
    }
}
int main(){
    int n=read(),m=read();
    for (register int i=1;i<=n;++i) val[i]=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    int rt=1;
    for (register int i=1;i<=m;++i){
        int opr=read();
        if (opr==1) rt=read();
        else {
            nowu=read();
            memset(col,0,sizeof(col));
            dfs(rt,rt,0);
            int ans=0;
            for (register int i=1;i<=n;++i){
                if (col[i]>1) ans+=col[i]*(col[i]-1)/2;
            }
            printf("%d\n",ans);
        }
    }
}

100pts

考虑莫队，首先，参考这篇题解，你就会发现这个换根是假的。

前两种情况，就是查询[1,n][1,n]和[L[u],R[u]][L[u],R[u]]直接放进一个莫队里面搞就可以了，但是别忘了还要查询[1,L[v]−1][1,L[v]-1]，[R[v]+1,n][R[v]+1,n]，如果ii，jj都在[1,L[v]−1][1,L[v]-1]，或者都在[R[v]+1,n][R[v]+1,n]还是可以套用上面的方法，如果ii在[1,L[v]−1][1,L[v]-1]，jj在[R[v]+1,n][R[v]+1,n]的话，怎么搞呢？

我想了一个笨办法，再开一个莫队就可以了，询问i∈[1,l],j∈[r,n]i \in[1,l],j \in [r,n]之间数对的个数，最后加起来就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
if (u==rt){
     AddQuery1(1,n,qu);
}
else if (LCA(u,rt)==u){
    int v=Hop(rt,u);
    if (L[v]>1) AddQuery1(1,L[v]-1,qu);
    if (R[v]<n) AddQuery1(R[v]+1,n,qu);
    AddQuery2(L[v]-1,R[v]+1,qu);
}
else {
    AddQuery1(L[u],R[u],qu);
}

献上写得很丑的标算，注意要开long long\text{long long}，我应该刻意卡了int\text {int}：

时间复杂度O(nn)O(n \sqrt n)

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <bits/stdc++.h>
#define MAXN 500005
#define MAXM 19
#define int long long
using namespace std;
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^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int L[MAXN],R[MAXN],dfn,seq[MAXN];
int anc[MAXN][MAXM],dep[MAXN];
int val[MAXN],n,m;
void dfs(int u,int father){
    seq[L[u]=++dfn]=val[u];
    anc[u][0]=father;
    for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father){
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
    R[u]=dfn;
}
inline int LCA(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
    }
    return anc[u][0];
}
inline int Hop(int u,int v){//h♂p to v's son
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>dep[v]){
            u=anc[u][i];
        }
    }
    return u;
}
int pos[MAXN],rt;
struct Query1{
    int l,r;//表示询问[l,r]内相同的数对个数
    int id;
}q1[MAXN];
inline bool operator < (const Query1 &a,const Query1 &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
struct Query2{
    int l,r;//表示询问[1,l][r,n]之间相同数对的个数
    int id;
}q2[MAXN];
inline bool operator < (const Query2 &a,const Query2 &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int c1,c2;
inline void AddQuery1(int l,int r,int id){q1[++c1]=Query1{l,r,id};}
inline void AddQuery2(int l,int r,int id){q2[++c2]=Query2{l,r,id};}
int cnt[MAXN];
int cnt1[MAXN],cnt2[MAXN];
long long Ans[MAXN],ans;
inline void Add(int x){
    ++cnt[x],ans+=(cnt[x]-1);//除去自己
}
inline void Del(int x){
    ans-=(cnt[x]-1),--cnt[x];
}
#undef int
int main(){
#define int long long
    n=read(),m=read();
    for (register int i=1;i<=n;++i){
        val[i]=read();
    }

    int Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        pos[i]=(i-1)/Size+1;
    }

    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(1,1);
	 
    rt=1;
    int qu=0;
    for (register int i=1;i<=m;++i){
        int opr=read();
        if (opr==1){
            rt=read();
        }
        else {
            qu++;
            int u=read();
            if (u==rt){
                AddQuery1(1,n,qu);
            }
            else if (LCA(u,rt)==u){
                int v=Hop(rt,u);
                if (L[v]>1) AddQuery1(1,L[v]-1,qu);
                if (R[v]<n) AddQuery1(R[v]+1,n,qu);
                AddQuery2(L[v]-1,R[v]+1,qu);
            }
            else {
                AddQuery1(L[u],R[u],qu);
            }
        }
    }
    //to compelete Query1
    sort(q1+1,q1+1+c1);
    int l=1,r=0;
    ans=0;
    for (register int i=1;i<=c1;++i){
        while (l<q1[i].l) Del(seq[l++]);
        while (l>q1[i].l) Add(seq[--l]);
        while (r<q1[i].r) Add(seq[++r]);
        while (r>q1[i].r) Del(seq[r--]);
        Ans[q1[i].id]+=ans;
    }

    //to compelete Query2
    sort(q2+1,q2+1+c2);
    l=0,r=n+1;
    ans=0;
    for (register int i=1;i<=c2;++i){
        while (l<q2[i].l){
            ++cnt1[seq[++l]];
            ans+=cnt2[seq[l]];
        }
        while (l>q2[i].l){
            --cnt1[seq[l]];
            ans-=cnt2[seq[l--]];
        }
        while (r<q2[i].r){
            --cnt2[seq[r]];
            ans-=cnt1[seq[r++]];
        }
        while (r>q2[i].r){
            ++cnt2[seq[--r]];
            ans+=cnt1[seq[r]];
        }
        Ans[q2[i].id]+=ans;
    }
    for (register int i=1;i<=qu;++i){
        printf("%lld\n",Ans[i]);
    }
}

这道题O(nlog⁡n)O(n \log n)预处理O(1)O(1)查询的方法应该也有，但是我太菜了，不想写。

你们写出来就可以爆碾标算了。

最后一个点出锅了，正在修复

相关文章
AT1219 歴史の研究BZOJ 4358 permuP1903 [国家集训队]数颜色 / 维护队列P3674 小清新人渣的本愿基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/4b58a367.html

更新于：2022年6月14日

题解

莫队

评论