杂题小记（2023.03.01）

更好的阅读体验戳此进入

[ARC084D] Small Multiple

题面

给定 $k$$k$ 求一个 $k$$k$ 的正整数倍数 $S$$S$ 使得 $S$$S$ 的数位和最小，输出数位和。

Solution

依然考虑类似同余最短路的思路，每个点表示模 $k$$k$ 余 $i$$i$，显然有两种操作，即将原数 $+1$$+1$，$i\to (i+1)modk$$i \to (i + 1) \bmod k$，贡献为 $1$$1$。以及将原数 $\times 10$$\times 10$，即 $i\to (i\times 10)modk$$i \to (i \times 10) \bmod{k}$，贡献为 $0$$0$，建边后从 $1$$1$ 到 $0$$0$ 跑最短路即可，特别地由于本题特殊性亦可使用 01BFS 解决。

Code

xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int K;
27
bitset < 110000 > vis;
28
int dis[110000];
29

30
void bfs(void){
31
    memset(dis, 0x3f, sizeof dis);
32
    deque < int > cur;
33
    vis[1] = true, dis[1] = 1;
34
    cur.push_front(1);
35
    while(!cur.empty()){
36
        int p = cur.front(); cur.pop_front();
37
        if(auto val = p * 10 % K; !vis[val]){
38
            vis[val] = true;
39
            dis[val] = min(dis[val], dis[p]);
40
            cur.push_front(val);
41
        }
42
        if(auto val = (p + 1) % K; !vis[val]){
43
            dis[val] = min(dis[val], dis[p] + 1);
44
            cur.push_back(val);
45
        }
46
    }
47
}
48

49
int main(){
50
    K = read();
51
    bfs();
52
    printf("%d\n", dis[0]);
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

LG-P2371 [国家集训队]墨墨的等式

题面

给定序列 $a_n$$a_n$ 和 $l,r$$l, r$，求有多少 $b\in [l,r]$$b \in [l, r]$ 满足 $\sum _{i=1}^n{a}_i{x}_i=b$$\sum_{i = 1}^n a_ix_i = b$ 存在非负整数解。

Solution

经典同余最短路，和跳楼机那题没什么区别，对 $r$$r$ 和 $l-1$$l - 1$ 分别求然后减一下即可。

Code

xxxxxxxxxx
94
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    ll val;
32
    OPNEW;
33
}ed[7100000];
34
ROPNEW;
35
Edge* head[510000];
36

37
int N;
38
int P;
39
ll l, r;
40
int A[510000];
41
ll dis[510000];
42
ll ans(0);
43
bitset < 510000 > vis;
44

45
void Dijkstra(void){
46
    memset(dis, 0x3f, sizeof dis);
47
    priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > cur;
48
    dis[0] = 0, cur.push({0, 0});
49
    while(!cur.empty()){
50
        int p = cur.top().second; cur.pop();
51
        if(vis[p])continue;
52
        vis[p] = true;
53
        for(auto i = head[p]; i; i = i->nxt)
54
            if(dis[SON] > dis[p] + i->val)
55
                dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
56
    }
57
}
58

59
int main(){
60
    N = read(), l = read < ll >(), r = read < ll >();
61
    for(int i = 1; i <= N; ++i)A[i] = read();
62
    P = A[1];
63
    for(int i = 0; i < P; ++i)
64
        for(int j = 2; j <= N; ++j)
65
            head[i] = new Edge{head[i], (i + A[j]) % P, A[j]};
66
    Dijkstra();
67
    ll H = r;
68
    for(int i = 0; i < P; ++i)
69
        if(H >= dis[i])
70
            ans += (H - dis[i]) / P + 1;
71
    H = l - 1;
72
    for(int i = 0; i < P; ++i)
73
        if(H >= dis[i])
74
            ans -= (H - dis[i]) / P + 1;
75
    printf("%lld\n", ans);
76
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77
    return 0;
78
}
79

80
template < typename T >
81
inline T read(void){
82
    T ret(0);
83
    int flag(1);
84
    char c = getchar();
85
    while(c != '-' && !isdigit(c))c = getchar();
86
    if(c == '-')flag = -1, c = getchar();
87
    while(isdigit(c)){
88
        ret *= 10;
89
        ret += int(c - '0');
90
        c = getchar();
91
    }
92
    ret *= flag;
93
    return ret;
94
}

LG-P2158 [SDOI2008] 仪仗队

题面

作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N\times N$$N \times N$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

Solution

不难发现答案转化为求所有横纵坐标在 $[1,n-1]$$[1, n - 1]$ 且互质的点的个数加 $2$$2$，可感性转化为 $\sum _{i=1}^{n-1}\phi (i)\times 2-1+2$$\sum_{i = 1}^{n - 1} \varphi(i) \times 2 - 1 + 2$，即对称讨论后减去主对角线上重复计算的。我们令 $n\leftarrow n-1$$n \leftarrow n - 1$，尝试通过交换求和严谨推导：

线性筛欧拉函数即可。

Code

xxxxxxxxxx
66
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (41000)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
int phi[LIM + 100];
30
int ans(0);
31
basic_string < int > Prime;
32
bitset < LIM + 100 > notPrime;
33

34
int main(){phi[1] = 1;
35
    for(int i = 2; i <= LIM; ++i){
36
        if(!notPrime[i])Prime += i, phi[i] = i - 1;
37
        for(auto p : Prime){
38
            if(i * p > LIM)break;
39
            phi[i * p] = i % p ? phi[i] * phi[p] : p * phi[i];
40
            notPrime[i * p] = true;
41
            if(i % p == 0)break;
42
        }
43
    }
44
    N = read();
45
    if(N == 1)printf("0\n"), exit(0);
46
    for(int i = 1; i <= N - 1; ++i)ans += phi[i] * 2;
47
    printf("%d\n", ans + 1);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

52
template < typename T >
53
inline T read(void){
54
    T ret(0);
55
    int flag(1);
56
    char c = getchar();
57
    while(c != '-' && !isdigit(c))c = getchar();
58
    if(c == '-')flag = -1, c = getchar();
59
    while(isdigit(c)){
60
        ret *= 10;
61
        ret += int(c - '0');
62
        c = getchar();
63
    }
64
    ret *= flag;
65
    return ret;
66
}

LG-P2568 GCD

题面

给定 $n$$n$，求满足 $gcd(x,y)$$\gcd(x, y)$ 为质数的有序数对 $(x,y)$$(x, y)$ 有多少种。

Solution

我们令 $m$$m$ 为值域在 $[1,n]$$[1, n]$ 的质数个数，朴素推导：

然后问题就转化为了 LG-P2158 [SDOI2008] 仪仗队，预处理一下即可。

Code

xxxxxxxxxx
69
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (11000000)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
int phi[LIM + 100];
30
ll ans(0);
31
ll sum[LIM + 100];
32
basic_string < int > Prime;
33
bitset < LIM + 100 > notPrime;
34

35
int main(){phi[1] = 1, notPrime[1] = true;
36
    for(int i = 2; i <= LIM; ++i){
37
        if(!notPrime[i])Prime += i, phi[i] = i - 1;
38
        for(auto p : Prime){
39
            if((ll)i * p > LIM)break;
40
            phi[i * p] = i % p ? phi[i] * phi[p] : p * phi[i];
41
            notPrime[i * p] = true;
42
            if(i % p == 0)break;
43
        }
44
    }N = read();
45
    for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + phi[i] * 2;
46
    for(auto p : Prime){
47
        if(p > N)break;
48
        ans += sum[N / p] - 1;
49
    }
50
    printf("%lld\n", ans);
51
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52
    return 0;
53
}
54

55
template < typename T >
56
inline T read(void){
57
    T ret(0);
58
    int flag(1);
59
    char c = getchar();
60
    while(c != '-' && !isdigit(c))c = getchar();
61
    if(c == '-')flag = -1, c = getchar();
62
    while(isdigit(c)){
63
        ret *= 10;
64
        ret += int(c - '0');
65
        c = getchar();
66
    }
67
    ret *= flag;
68
    return ret;
69
}

CF600E Lomsat gelral

题面

给定节点染色的树，对于每个节点询问其子树出现次数最多的颜色，有多个则输出颜色编号和。

Solution

dot 模板题，注意更新最大颜色时的一些细节即可。

Code

xxxxxxxxxx
105
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[210000];
34
ROPNEW;
35
Edge* head[110000];
36
int col[110000];
37
int siz[110000], hson[110000];
38
int cnt[110000];
39
ll ans[110000];
40
int mxp(0);
41
ll mxv(0);
42
queue < int > trash;
43

44
void dfs_pre(int p = 1, int fa = 0){
45
    siz[p] = 1;
46
    for(auto i = head[p]; i; i = i->nxt){
47
        if(SON == fa)continue;
48
        dfs_pre(SON, p);
49
        siz[p] += siz[SON];
50
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
51
    }
52
}
53
void Insert(int p){
54
    ++cnt[col[p]], trash.push(col[p]);
55
    if(mxp == col[p] || cnt[col[p]] > cnt[mxp])mxp = col[p], mxv = col[p];
56
    else if(cnt[col[p]] == cnt[mxp])mxv += col[p];
57
}
58
void InsertSubt(int p, int fa){
59
    Insert(p);
60
    for(auto i = head[p]; i; i = i->nxt)
61
        if(SON != fa)InsertSubt(SON, p);
62
}
63
void RemoveAll(void){
64
    while(!trash.empty())--cnt[trash.front()], trash.pop();
65
    mxp = mxv = 0;
66
}
67
void dfs_make(int p = 1, int fa = 0){
68
    for(auto i = head[p]; i; i = i->nxt)
69
        if(SON != fa && SON != hson[p])
70
            dfs_make(SON, p), RemoveAll();
71
    if(hson[p])dfs_make(hson[p], p);
72
    for(auto i = head[p]; i; i = i->nxt)
73
        if(SON != fa && SON != hson[p])
74
            InsertSubt(SON, p);
75
    Insert(p), ans[p] = mxv;
76
}
77

78
int main(){
79
    N = read();
80
    for(int i = 1; i <= N; ++i)col[i] = read();
81
    for(int i = 1; i <= N - 1; ++i){
82
        int s = read(), t = read();
83
        head[s] = new Edge{head[s], t};
84
        head[t] = new Edge{head[t], s};
85
    }dfs_pre(), dfs_make();
86
    for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
87
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88
    return 0;
89
}
90

91
template < typename T >
92
inline T read(void){
93
    T ret(0);
94
    int flag(1);
95
    char c = getchar();
96
    while(c != '-' && !isdigit(c))c = getchar();
97
    if(c == '-')flag = -1, c = getchar();
98
    while(isdigit(c)){
99
        ret *= 10;
100
        ret += int(c - '0');
101
        c = getchar();
102
    }
103
    ret *= flag;
104
    return ret;
105
}

LG-P4777 【模板】扩展中国剩余定理（EXCRT）

题面

同余式：

但是不满足 $m_1,m_2,\cdots ,m_n$$m_1, m_2, \cdots, m_n$ 之间两两互质。

求 $x$$x$ 的最小非负整数解。

Solution

虽然是 exCRT 但是除了问题相似之外与 CRT 似乎没什么关系。

首先考虑存在两个同余方程：

考虑对于线性同余方程的常规转化：

有：$a_1+b_1{m}_1=a_2+b_2{m}_2$$a_1 + b_1m_1 = a_2 + b_2m_2$，整理得到 $b_1{m}_1+(-b_2)m_2=a_2-a_1$$b_1m_1 + (-b_2)m_2 = a_2 - a_1$。

可以用 exgcd 求得 $b_1{m}_1+(-b_2)m_2=gcd(m_1,m_2)$$b_1m_1 + (-b_2)m_2 = \gcd(m_1, m_2)$ 的解 $b_1^{\prime },b_2^{\prime }$$b_1', b_2'$，同时有 $d={\displaystyle \frac{a_2-a_1}{gcd(m_1,m_2)}}$$d = \dfrac{a_2 - a_1}{\gcd(m_1, m_2)}$，于是有：

所以现在我们以 $x=a_1+b_1{m}_1$$x = a_1 + b_1m_1$ 为例，我们显然要最小化 $b_1$$b_1$，于是我们取方程中 $b_1^{\prime }$$b_1'$ 的最小非负解，或者说实际上取得应为 $d{b}_1^{\prime }$$db_1’$ 的最小非负解，即 $b_1=d{b}_1^{\prime }$$b_1 = db_1'$。

Tips：读到这里不难发现，若不满足 $gcd(m_1,m_2)\mid a_2-a_1$$\gcd(m_1, m_2) \mid a_2 - a_1$，则方程无解。

于是此时我们可以根据 $b$$b$ 得出一个满足上述两个同余方程的特解 $x^{\prime }$$x'$，且可以证明对于上述同余方程的所有解 $x$$x$，有 $x=x^{\prime }+k\mathrm{lcm}(m_1,m_2)$$x = x' + k \operatorname{lcm}(m_1, m_2)$，即：

此时两个方程被合成为了同一个，直到最终仅剩一个方程时其解即为答案。

Code

xxxxxxxxxx
74
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
void exgcd(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y){
27
    if(!b)return x = 1, y = 0, void();
28
    exgcd(b, a % b, x, y);
29
    __int128_t tmp(x);
30
    x = y;
31
    y = tmp - a / b * y;
32
}
33
void Query(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y, __int128_t c){
34
    exgcd(a, b, x, y);
35
    __int128_t d = c / __gcd(a, b);
36
    x *= d, y *= d;
37
    __int128_t val = b / __gcd(a, b);
38
    x = (x % val + val) % val;
39
    y = (c - a * x) - b;
40
}
41

42
int N;
43
__int128_t rem1(-1), mod1(-1);
44

45
int main(){
46
    N = read();
47
    while(N--){
48
        __int128_t mod2 = read < ll >(), rem2 = read < ll >();
49
        if(!~rem1 || !~mod1){rem1 = rem2, mod1 = mod2; continue;}
50
        __int128_t b1, b2;
51
        Query(mod1, -mod2, b1, b2, rem2 - rem1);
52
        rem1 = rem1 + b1 * mod1;
53
        mod1 = mod1 * mod2 / __gcd(mod1, mod2);
54
        rem1 = (rem1 % mod1 + mod1) % mod1;
55
    }printf("%lld\n", rem1);
56
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
57
    return 0;
58
}
59

60
template < typename T >
61
inline T read(void){
62
    T ret(0);
63
    int flag(1);
64
    char c = getchar();
65
    while(c != '-' && !isdigit(c))c = getchar();
66
    if(c == '-')flag = -1, c = getchar();
67
    while(isdigit(c)){
68
        ret *= 10;
69
        ret += int(c - '0');
70
        c = getchar();
71
    }
72
    ret *= flag;
73
    return ret;
74
}

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

题面

给定树，边权为 $a$$a$ 到 $v$$v$ 之间的字符，对于每个子树求最长路径满足所有边上的字符可以在重新排列后组成一个回文串。

Solution

属于是 dot 里难度较高的题了。

最开始以为求的是子树所有边的答案，光速糊了一个上去然后第三个点就挂了，又看了一遍题才发现这东西求的是路径。。

该说不说这个题意看着总有点像点分治。

首先考虑回文串的性质，不难发现只要满足对于所有种类的字符，最多有一种字符数量为奇数则可以构成回文串，且发现共 $22$$22$ 个字符，不难想到对其进行状压，用一个 $2^{22}-1$$2^{22} - 1$ 大小的状态表示每一位对应的字符是否为奇数（注意需要边权下放到点权），同时不难发现仅有 $0$$0$ 或 $2^k$$2^k$ 的状态是合法的。

而对于两个状态的合并，也不难发现满足异或的性质。

于是我们考虑记 $statu{s}_p$$status_p$ 表示从 $1$$1$ 到 $p$$p$ 的前缀异或，这样当我们合并两条路径，也就是 $statu{s}_x\oplus statu{s}_y$$status_x \oplus status_y$ 的时候，从根节点到其 LCA 的路径会因异或的性质被抵消，这也就是快速维护可以成立的关键之处。

发现共需要讨论三种情况，子树内的路径，一个端点在子树根的路径，两个端点都在子树内但经过子树根的路径。

对于后两种的维护，考虑记录 $mxde{p}_s$$mxdep_s$ 表示 $s$$s$ 状态下的当前存在的边中的最大深度，这样贪心显然是正确的。以此按照一般 dot 套路跑一下即可，细节较多，还是很有启发性的一道题的。

Code

xxxxxxxxxx
110
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define INF (0x3f3f3f3f)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[1100000];
34
ROPNEW;
35
Edge* head[510000];
36
int dep[510000], siz[510000], hson[510000];
37
int ans[510000];
38
int mxdep[4500000], status[510000];
39

40
void dfs_pre(int p = 1, int fa = 0){
41
    siz[p] = 1, dep[p] = dep[fa] + 1, status[p] ^= status[fa];
42
    for(auto i = head[p]; i; i = i->nxt){
43
        if(SON == fa)continue;
44
        dfs_pre(SON, p);
45
        siz[p] += siz[SON];
46
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
47
    }
48
}
49
void ClearAll(int p, int fa){
50
    mxdep[status[p]] = -INF;
51
    for(auto i = head[p]; i; i = i->nxt)
52
        if(SON != fa)ClearAll(SON, p);
53
}
54
void Update(int p, int fa, int rt){
55
    ans[rt] = max(ans[rt], dep[p] + mxdep[status[p]]);
56
    for(int i = 0; i <= 21; ++i)ans[rt] = max(ans[rt], dep[p] + mxdep[status[p] ^ (1 << i)]);
57
    for(auto i = head[p]; i; i = i->nxt)
58
        if(SON != fa)Update(SON, p, rt);
59
}
60
void Insert(int p, int fa){
61
    mxdep[status[p]] = max(mxdep[status[p]], dep[p]);
62
    for(auto i = head[p]; i; i = i->nxt)
63
        if(SON != fa)Insert(SON, p);
64
}
65
void dfs_make(int p = 1, int fa = 0){
66
    for(auto i = head[p]; i; i = i->nxt)
67
        if(SON != fa && SON != hson[p])dfs_make(SON, p), ClearAll(SON, p);
68
    if(hson[p])dfs_make(hson[p], p);
69
    for(auto i = head[p]; i; i = i->nxt)
70
        if(SON != fa && SON != hson[p])Update(SON, p, p), Insert(SON, p);
71
    mxdep[status[p]] = max(mxdep[status[p]], dep[p]);
72
    ans[p] = max(ans[p], dep[p] + mxdep[status[p]]);
73
    for(int i = 0; i <= 21; ++i)
74
        ans[p] = max(ans[p], dep[p] + mxdep[status[p] ^ (1 << i)]);
75
    ans[p] -= dep[p] << 1;
76
    for(auto i = head[p]; i; i = i->nxt)
77
        if(SON != fa)ans[p] = max(ans[p], ans[SON]);
78
}
79

80
int main(){
81
    for(int i = 0; i < 4500000; ++i)mxdep[i] = -INF;
82
    N = read();
83
    for(int i = 2; i <= N; ++i){
84
        int s = read(), t = i;
85
        char c = getchar(); while(!islower(c))c = getchar();
86
        status[t] = 1 << (c - 'a');
87
        head[s] = new Edge{head[s], t};
88
        head[t] = new Edge{head[t], s};
89
    }dfs_pre(), dfs_make();
90

91
    for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
92
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93
    return 0;
94
}
95

96
template < typename T >
97
inline T read(void){
98
    T ret(0);
99
    int flag(1);
100
    char c = getchar();
101
    while(c != '-' && !isdigit(c))c = getchar();
102
    if(c == '-')flag = -1, c = getchar();
103
    while(isdigit(c)){
104
        ret *= 10;
105
        ret += int(c - '0');
106
        c = getchar();
107
    }
108
    ret *= flag;
109
    return ret;
110
}

CF1009F Dominant Indices

题面

给定一棵以 $1$$1$ 为根，$n$$n$ 个节点的树。设 $d(u,x)$$d(u,x)$ 为 $u$$u$ 子树中到 $u$$u$ 距离为 $x$$x$ 的节点数。

对于每个点，求一个最小的 $k$$k$，使得 $d(u,k)$$d(u,k)$ 最大。

Solution

很板子的 dot，注意需要一个类似 CF741D 的思路，记录 $dep$$dep$ 后在答案里减去根的 $dep$$dep$。

Code

xxxxxxxxxx
102
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[2100000];
34
ROPNEW;
35
Edge* head[1100000];
36
int siz[1100000], hson[1100000], dep[1100000];
37
int cnt[1100000];
38
ll ans[1100000];
39
int mxp(0);
40
queue < int > trash;
41

42
void dfs_pre(int p = 1, int fa = 0){
43
    siz[p] = 1, dep[p] = dep[fa] + 1;
44
    for(auto i = head[p]; i; i = i->nxt){
45
        if(SON == fa)continue;
46
        dfs_pre(SON, p);
47
        siz[p] += siz[SON];
48
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
49
    }
50
}
51
void Insert(int p){
52
    ++cnt[dep[p]], trash.push(dep[p]);
53
    if(cnt[dep[p]] > cnt[mxp])mxp = dep[p];
54
    else if(cnt[dep[p]] == cnt[mxp])mxp = min(mxp, dep[p]);
55
}
56
void InsertSubt(int p, int fa){
57
    Insert(p);
58
    for(auto i = head[p]; i; i = i->nxt)
59
        if(SON != fa)InsertSubt(SON, p);
60
}
61
void RemoveAll(void){
62
    while(!trash.empty())--cnt[trash.front()], trash.pop();
63
    mxp = 0;
64
}
65
void dfs_make(int p = 1, int fa = 0){
66
    for(auto i = head[p]; i; i = i->nxt)
67
        if(SON != fa && SON != hson[p])
68
            dfs_make(SON, p), RemoveAll();
69
    if(hson[p])dfs_make(hson[p], p);
70
    for(auto i = head[p]; i; i = i->nxt)
71
        if(SON != fa && SON != hson[p])
72
            InsertSubt(SON, p);
73
    Insert(p), ans[p] = mxp - dep[p];
74
}
75

76
int main(){
77
    N = read();
78
    for(int i = 1; i <= N - 1; ++i){
79
        int s = read(), t = read();
80
        head[s] = new Edge{head[s], t};
81
        head[t] = new Edge{head[t], s};
82
    }dfs_pre(), dfs_make();
83
    for(int i = 1; i <= N; ++i)printf("%lld\n", ans[i]);
84
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
85
    return 0;
86
}
87

88
template < typename T >
89
inline T read(void){
90
    T ret(0);
91
    int flag(1);
92
    char c = getchar();
93
    while(c != '-' && !isdigit(c))c = getchar();
94
    if(c == '-')flag = -1, c = getchar();
95
    while(isdigit(c)){
96
        ret *= 10;
97
        ret += int(c - '0');
98
        c = getchar();
99
    }
100
    ret *= flag;
101
    return ret;
102
}