Codeforces Round 911 (Div. 2)（C~E）（DFS、数论（容斥）、SCC缩点 + DAG图上DP）

本文介绍: 题意：凯克西奇一直被安吉冷落。通过一个共同的朋友，他发现安吉非常喜欢二叉树，于是决定解决她的问题，以引起她的注意。Anji 给了 Ke ks ic 一棵有 n个顶点的二叉树。顶点 1 是根，没有父顶点。所有其他顶点都有一个父顶点。每个顶点最多可以有 2个子顶点、一个左子顶点和一个右子顶点。对于每个顶点，安吉都会告诉凯西奇它的左子和右子的索引，或者告诉他它们不存在。此外，每个顶点上都有一个字母，即 “U”、”L “或 “R”。

1900C – Anji’s Binary Tree

题意：

凯克西奇一直被安吉冷落。通过一个共同的朋友，他发现安吉非常喜欢二叉树，于是决定解决她的问题，以引起她的注意。Anji 给了 Ke ks ic 一棵有 n个顶点的二叉树。顶点 1 是根，没有父顶点。所有其他顶点都有一个父顶点。每个顶点最多可以有 2个子顶点、一个左子顶点和一个右子顶点。对于每个顶点，安吉都会告诉凯西奇它的左子和右子的索引，或者告诉他它们不存在。

此外，每个顶点上都有一个字母 $eq?s_%7Bi%7D$ ，即 “U”、”L “或 “R”。

克克西奇从根开始下棋，他的每一步都是这样走的：

如果当前顶点上的字母是 “U”，他就移动到它的父顶点。如果它不存在，他就什么也不做。
如果当前顶点上的字母是 “L”，则移动到其左侧子顶点。如果它不存在，则他什么也不做。
如果当前顶点上的字母是 “R”，则移动到其右边的子顶点。如果它不存在，则他什么也不做。

在移动之前，他可以执行以下操作：选择任意一个节点，并用另一个节点替换写在上面的字母。

我们想知道的是，当他开始旅行时，他将在某一点到达一片叶子，那么他在旅行前需要做的操作的最小数目。叶子是一个没有子顶点的顶点。他到达哪片叶子并不重要。需要注意的是，他是否会停留在叶子上并不重要，他只需要移动到叶子上。此外，他需要移动多少次才能到达一片叶子也无关紧要。

帮助 Ke k s i c 解开安吉的树，这样他就能赢得她的芳心，让她来到恰恰克。

思路：转化为到叶子结点最短路，若顶点字母是‘L’，则到达左孩子路径长度为0，若顶点是‘R’，则到达右边孩子长度为0，否则都是1（代表了需要修改），求到达叶子结点路径最小值。

// Problem: C. Anji's Binary Tree
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/C
// Memory Limit: 256 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include &lt;bits/stdc++.h&gt;
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f;
const LL llinf = 5e18;
typedef pair&lt;int,int&gt;pl;
priority_queue&lt;LL , vector&lt;LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct Node{
	int l ,  r;
}e[N];
void solve() 
{
	cin >> n;
	string s;
	cin >> s;
	s = " " + s;
//	cout << s[1]<<endl;
	for(int i = 1 ; i <= n ; i ++){
		cin >> e[i].l >> e[i].r;	
	}
	int ans = inf;
	queue< pair<int,int>>q;
	q.push({1 , 0});
	while(!q.empty()){
		auto tmp = q.front();
		q.pop();
		int id = tmp.x , dis = tmp.y;
//		cout << id << dis << endl;
		if(e[id].l != 0){
			int nex = e[id].l;
			if(s[id] != 'L'){
				q.push({nex , dis + 1});
			}
			else{
				q.push({nex , dis});
			}
		}
		if(e[id].r != 0){
			int nex = e[id].r;
			if(s[id] != 'R'){
				q.push({nex , dis + 1});
			}
			else{
				q.push({nex , dis});
			}			
		}
		if(e[id].l == 0 &amp;&amp; e[id].r == 0){
			ans = min(ans , dis);
		}
	}
	cout << ans << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

1900D – Small GCD

（太菜了导致坐牢一个半小时，没想到能够预处理因子的价值，下次不会再犯了）

题意：设 a 、 b 和 c 为整数。函数 f(a,b,c) 的定义如下：将数字 a 、 b 、 c 排序为 a≤b≤c 。然后返回 gcd(a,b) ，其中 gcd(a,b) 表示整数 a 和 b 的最大公约数 (GCD)。给你一个由 n 个元素组成的数组 a 。计算每个 i 、 j 、 k 的 f(ai,aj,ak) 和，使得 1≤i<j<k≤n 。更正式地说，计算

$eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bn%7D%20%5Csum_%7Bj%20%3D%20i%20+%201%7D%5E%7Bn%7D%20%5Csum_%7Bk%20%3D%20j%20+%201%7D%5E%7Bn%7Df%28a_%7Bi%7D%2Ca_%7Bj%7D%2C%20a_%7Bk%7D%29$ 。

思路：当对a数组进行排序以后会发现，原式子 $eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bn%7D%20%5Csum_%7Bj%20%3D%20i%20+%201%7D%5E%7Bn%7D%20%5Csum_%7Bk%20%3D%20j%20+%201%7D%5E%7Bn%7Df%28a_%7Bi%7D%2Ca_%7Bj%7D%2C%20a_%7Bk%7D%29$ 的k变成了一个无效的东西（因为 $eq?a_%7Bi%7D%20%5Cleq%20a_%7Bj%7D%5Cleq%20a_%7Bk%7D$ ）。原式子变为 $sum_{i = 1}^{n} sum_{j = i + 1}^{n} gcd(a_{i},a_{j})*(n - j)$

再转化一下得到 $eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bj%20-%201%7D%20%5Csum_%7Bj%20%3D%202%7D%5E%7Bn%7D%20gcd%28a_%7Bi%7D%2Ca_%7Bj%7D%29*%28n%20-%20j%29$ .。对于这种所有区间求和问题，考虑右端点递增，然后思考如何去维护左侧所有区间的信息。首先我们如果单纯的两两求gcd肯定是不行的，观察数据后发现a数组的数据很小，也就是说a的因子个数很小。而两个数的gcd也就是他们的最大公共因子。因此可以考虑统计区间内所有因子的个数，然后对于每个右端点 $eq?a_%7Bj%7D$ 而言，遍历其所有因子，区间之和就是（右端点的因子大小 * 区间内该因子的个数）的总和。但是仔细想想之后发现是有重复的：假如当前因子是2，用2 * 区间内2的因子个数是不正确的，因为有2这个因子也必然会有1这个因子。gcd是两个数的最大公共因子，所以统计因子2时会把1这个因子给撤销掉，后面任意因子也是同理。也就是说，2这个因子的实际价值不是2而是1。3也是同理，3的实际价值需要减去1的实际价值，而6的实际价值需要减去1、2、3实际价值。因此对于任意一个因子而言，其实际价值需要需要减去其所有不为他本身的因子的实际价值。

对于每个数的因子，每个因子的实际价值都是可以预处理出来的。做的时候只需要过一下公式即可。

// Problem: D. Small GCD
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 1e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
int cnt[N];
vector<int>yinzi[100010];
int val[N];
void solve() 
{
	memset(cnt , 0 , sizeof cnt);
	cin >> n;
	for(int i = 0 ; i < n ; i ++)
		cin >> a[i];
	sort(a , a + n);
	LL ans = 0;
	for(int i = 0 ; i < n - 1; i ++){
		LL sum = 0;
		for(auto it : yinzi[a[i]])
			sum += 1LL * val[it] * cnt[it];
		ans += sum * (n - i - 1);
		for(auto it : yinzi[a[i]]){
			cnt[it]++;
		}		
	}
	cout << ans <<endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
    int maxx = -1;
	auto cmp = [&amp;](int x , int y){
		return x > y;
	};
	for(int i = 1 ; i <= 100000 ; i ++){
		val[i] = i;
		yinzi[i].pb(i);
	}
	for(int i = 1 ; i <= 100000; i ++){
		for(int j = i * 2; j <= 100000 ; j += i){
			yinzi[j].pb(i);
			val[j] -= val[i];
		}
	}
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

E – Transitive Graph

（补的时候发现就是个SCC缩点 + DAG图上DP问题）

题意：给你一个有向图 G ，其中有 n 个顶点和 m条边。

最初，图 H与图 G相同。然后，您决定执行以下操作：

如果存在由顶点 a 、 b 、 c 和 H 组成的三重顶点，且存在一条从 a 到 b 的边和一条从 b 到 c 的边，但没有从 a 到 c 的边，则添加一条从 a 到 c的边。
只要存在这样的三边形，就重复上一步。

注意，执行上述操作后， H中的边的数量最多可达 $eq?n%5E2$ 。

您还在图 H的顶点上写了一些值。更确切地说，在顶点 i 上写入了 ai的值。

考虑一条由 k个顶点组成的简单路径。索引为 v1,v2,…,vk 的个不同顶点组成的简单路径。这条路径的长度为 k 。该路径的值定义为 $eq?%5Csum%20_%7Bi%20%3D%201%7D%5Eka_%7Bv_%7Bi%7D%7D$ 。

如果图中没有其他更长的简单路径，那么这条简单路径就是最长的。

在 H中所有最长的简单路径中，找出数值最小的一条。

思路：观察题目中的操作，其实就是把有向图中一条路径上的点全部两两相连，~~其实这样操作在求最长简单路径时没有任何意义，因为a到c增加的边在求最长路径时必然会被a到b，b到c这两条边代替。~~这么做保证了能从一个强连通分量上的任意一点连到其他强连通分量上的任意一点。因此本题就变成了给定一个有向图求最长简单路径中权值最小的那一条。直接强连通分量缩点 + 图上DP就行，用tarjan求出scc，然后按照逆拓扑序dp就行。

// Problem: E. Transitive Graph
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
LL a[N];
vector<int>e[N];
int dfn[N] , low[N] , ins[N] , idx = 0 , cnt = 0, bel[N];//dfn : dfs的时间戳 low : 子树能跳到的最上方的点 bel : 结点位于哪块强连通分量上
stack<int>stk;
int out[N];
int x[N] , y[N] , ty[N] , ans = 0;
pair<LL,LL>dp[N];
void init(int n){
	idx = cnt = 0;
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0 , low[i] = 0 , ins[i] = 0 , bel[i] = 0 , dfn[i] = 0 , e[i].clear();
	}
}
void tarjan(int u , int fa){//无向图需要fa != u
	dfn[u] = low[u] = ++idx;//dfs序中的顺序
	ins[u] = true;//是否在栈当中
	stk.push(u);//未被切掉的点
	for(auto v : e[u]){
		if(!dfn[v]){
			tarjan(v , u);
			low[u] = min(low[u] , low[v]);
		}
		else{//被访问过了
			if(ins[v]){
				low[u] = min(low[u] , dfn[v]);
			}																																																																																																																																																																							
		}
	}
	if(dfn[u] == low[u]){
		cnt ++;
		int sz = 0;
		LL ch = 0;
		LL sum = 0;
		dp[cnt] = {0 , 0};
		while(true){
			int v = stk.top();
			bel[v] = cnt;
			ch ++;
			sum += a[v];
			ins[v] = false;
			for(int w : e[v]){
				if(bel[w] != cnt &amp;&amp; bel[w] != 0){
					if(dp[bel[w]].x > dp[cnt].x){
						dp[cnt] = dp[bel[w]];
					}
					else if(dp[bel[w]].x == dp[cnt].x &amp;&amp; dp[bel[w]].y < dp[cnt].y){
						dp[cnt] = dp[bel[w]];
					}
				}
			}
			stk.pop();
			if(v == u){
				break;
			}
		}
		dp[cnt].x += ch;
		dp[cnt].y += sum;
	}
}
void solve() 
{
	cin >> n >> m;
	map<pair<int,int>,int>mp;
	for(int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	for(int i = 0 ; i < m ; i ++){
		int x , y;
		cin >> x >> y;
		if(mp.count({x , y}) || x == y){
			continue;
		}
		else{
			e[x].pb(y);
			mp[{x,y}] = 1;
		}
	}
	for(int i = 1 ; i <= n ; i++){
		if(!dfn[i]) tarjan(i , 0);
	}
/*	for(int i = 1 ; i <= n ; i ++){
		cout << bel[i] << endl;
	}*/
	pair<LL,LL>ans = {0 , 0};
	for(int i = 1 ; i <= cnt ; i ++){
		if(dp[i].x > ans.x){
			ans = dp[i];
		}
		else if(dp[i].x == ans.x && dp[i].y < ans.y){
			ans = dp[i];
		}
	}
	init(n);
	cout << ans.x << " " << ans.y << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}