A. 为什么要演奏春日影！！！

题目大意

​一共n个音符，对于每个音符，可以获得的捉弄值是, 但是如果在找到这个音符前先找到了音符, 则获取的捉弄值是, 问在找到所有音符后对大祥老师的捉弄值最大是多少。

解题思路

​为了获取最大值, 我们可以想到需要尽可能多的拿到值, 而在找到音符i前先找到了音符, 就可以得到, 因此可以用一个数组来保存每个音符的值, 表示建一条边从到i. 而题目又保证每个音符i的值除了0以外是互不相等的, 因此可以得到建边以后只有链或者环, 然后就分情况讨论:

​如果是一条链, 那么只有第一个音符获取的捉弄值是, 后面的音符获取的捉弄值都是.

​如果是环, 那么必然要找到一个断点, 然后按照链的方式做, 问题就变成了该在哪里断链. 一种方式是可以直接拿暴力跑, 将环里面所有的音符都放到一个vector里面, 所有值累加起来存到sum中, 然后再遍历一遍环, 找到的最大值就是该环获得的捉弄值的最大值. 另一种方式是可以在的基础上再推一推, 要获取, 将变形成,是不变的, 也就得到了求的最小值.

完整代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int M = 1e6 + 10;
int n;
int a[M], b[M], c[M], ne[M];
bool st[M];

void solve(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i] >> b[i] >> c[i];
    ne[b[i]] = i;
  }

  int res = 0;
  for(int i = 1; i <= n; i++){
    if(b[i] == 0){
      res += a[i];
      st[i] = true;
      int t = ne[i];
      while(t != 0){
        st[t] = true;
        res += c[t];
        t = ne[t];
      }
    }
  }

  for(int i = 1; i <= n; i++){
    if(st[i]) continue;
    int t = i, sum = 0;
    int mn = 1e18;

    while(t != 0 && !st[t]){
      res += c[t];
      mn = min(mn, c[t] - a[t]);
      st[t] = true;
      t = ne[t];
    }

    res -= mn;
  }
  cout << res << endl;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int T = 1;
  while(T--){
    solve();
  }

  return 0;
}

B. 大模拟

解题思路

做法：贪心，模拟

​首先我们可以通过模拟求出数组中每一个数变化为另外一个数所需要的最少操作 和操作 的数量。我们定义三个数组 ，若一个数字 可以通过 次操作 和 次操作 变为 ，那么。

​通过模拟我们可以发现，每个数字通过操作1和操作2能变成的不同数字不会超过个，所以 个数字进行模拟的复杂度就是 。最后我们遍历 中的每个数字，假设当前遍历的数字为 ，若 ，则说明该数组中的 个元素可以经过 和 次操作 变为数字 。最后我们取一个满足条件的最小 即为答案。

​时间复杂度： 。

完整代码

#include<iostream>
#include<cstring>
#include<queue>
#include<cstring>
#include<map>
#include<string>
#include<cmath>
#include<stack>
#include<vector>
#include<unordered_map>
using namespace std;
#define int long long
#define endl '\n'
#define double long double
typedef pair<int, int> PII;
const int N = 2e6 + 10;
int nums[N];
int vis[N], vis2[N], vis3[N];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
	}
	for (int i = 1; i <= n; i++) {
		int num = 0, tmp = nums[i];
		int flag = 0;
		while (1) {
			vis3[tmp]++;
			vis[tmp] += num, vis2[tmp] += num;
			if (tmp == 0) break;
			num++;
			if (tmp % 2 != 0 && tmp / 2 >= 1) {
				int num2 = 1, tmp2 = tmp / 2 * 2;
				while (1) {
					vis3[tmp2]++;
					vis2[tmp2] += num;
					vis[tmp2] += num;
					vis[tmp2] -= num2;
					if (tmp2 > 1e6) break;
					num2++;
					tmp2 *= 2;
				}
			}
			tmp /= 2;
		}
		tmp = nums[i] * 2, num = 1;
		while (1) {
			vis3[tmp]++;
			vis[tmp] -= num;
			if (tmp > 1e6) break;
			num++;
			tmp *= 2;
		}
	}
	int res = 1e18, res2 = 0;
	for (int i = 1; i <= 1e6; i++) {
		if (vis[i] == 0 && vis3[i] == n) {
			res = min(vis2[i], res);
		}
	}
	if (res == 1e18) {
		res = -1;
	}
	cout << res << endl;
}
signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--) {
		solve();
	}
}

C.谁能留下呢

题目大意

​给定名同学以及他们的做题数，按照做题数量从大到小排名，排名在前的同学可以留下。次询问，询问具体某位同学能否留下。

解题思路

​对于每次询问，首先查找到该同学的做题数量，使用直接查询（本题数据范围也允许使用循环暴力查找）。然后循环暴力查找做题数大于的学院数量记为, 如果 输出 , 否则输出 。

完整代码

#include <stdio.h>
#include <string.h>
int main() {
    int n;
    char str[1010][35];
    int a[10000];
    scanf("%d", &n);
    int i;
    for (i = 1; i <= n; i++) {
        scanf("%s", str[i]);
        scanf("%d", &a[i]);
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        char s[35];
        scanf("%s", s);
        int ans;
        for (i = 1; i <= n; i++) {
            int flag = 0;
            if (strlen(s) != strlen(str[i])) continue;
            for (int j = 0; j < strlen(s); j++) {
                if (s[j] != str[i][j]) flag = 1;
            }
            if (flag == 0) {
                ans = a[i];
                break;
            }
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] > ans) cnt++;
        }
        if (cnt + 1 > (int) (n * 0.3)) {
            puts("NO");
        } else puts("YES");
    }
}

D.薇尔莉特能拿多少棵碧根果

题目大意

给了一个图，问你从哪些点出发可以拿到最多的碧根果。输出能拿到最多碧根果的点出发的点的个数。还有最多可以拿碧根果的数量

解题思路

本题的核心其实是想考拓扑。因为每个点离开后又会恢复到个碧根果的缘故。所以说如果有环，那么就可以一直在环里走，直到拿到个碧根果。如果某个点可以走进环里，那么显然它也是可以在环里一直走，直到拿到个碧根果。所以我们可以将点分为进环点（能走进环的点）和环上的点，和出环点（从环里面走出去的点）。按照前面的讨论，进环点和环点是一定满足条件的，那么只剩下判断出环点是否满足条件。对于出环点，那就是贪心的去到能拿碧根果最多的地点。由于拓扑的性质正向建边是可以将环点和出环点拓扑出来的，那为了将进环点和环点处理出来，我们可以反向建边。如果这题能想到反向建边，剩下的处理也就自然而然的出来了。在反向建边拓扑的时候可以顺便将每个点能拿到的最多的碧根果处理出来。这样拓扑一次就可以将所有信息都处理完了。

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const int INF = 100000000;
int h[N], e[N], ne[N], idx;
int a[N], d[N];
int n, m;
vector<int> add_val[N];
void add(int a ,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topo()
{
    queue<int> q;
    for(int i = 1; i <= n; i++) 
        if(d[i] == 0) q.push(i);
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int mx = 0;
        if(add_val[t].size() > 0) mx = *max_element(add_val[t].begin(), add_val[t].end());
        a[t] += mx;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0) q.push(j);
            add_val[j].push_back(a[t]);
        }
    }
}
void Grainrain()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) h[i] = -1;
    for(int i = 1; i <= n; i++) cin >> a[i];
    while(m--)
    {
        int u, v; cin >> u >> v;
        add(v, u);
        d[u]++;
    }
    topo();
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i] >= INF || d[i] > 0) cnt++;
    }
    if(cnt == 0)
    {
    	int mx = -INF;
    	for(int i = 1; i <= n; i++) mx = max(mx, a[i]);
    	for(int i = 1; i <= n; i++)
    		if(mx == a[i])
    			cnt++;
    	cout << cnt << endl;
    	cout << mx << endl;
	}
    else 
    {
    	cout << cnt << endl;
    	cout << INF << endl;
	}
}

signed main()
{
    Grainrain();
    return 0;
}

E 蓟县

题目大意：

......

解题思路

对于常数,

即输出次即可

完整代码

#include <iostream>

int main(){
    int n;
    std::cin >> n;

    for(int i = 0; i < n; i++) {
        std::cout << "Wuhan Institute of Technology\n";
    }
    return 0;
}

F.Companion

题目大意

背包容量为_，一共有个物品，第个物品和第物品的重量均为，求最后有多少种方案可以刚好装满背包

解题思路

本题为背包问题求解方案数

将目标分数看作背包容量， 每个任务的分数看作体积为、价值为的物品，由于同一个任务可以被两个人同时做，则可以将每个任务的分数看作两个体积为、价值为的物品，则一共有个物品

令体积达到时的方案数为，第个物品的体积为，价值为，如果此时是01背包问题求最大值，初始条件，则转移方程为

由于此时物品的价值和体积等价，则，公式可变形为

但本题是求解方案数，直接将问题从求最大值转换成求和即可，此时初始条件，即容量为时，一个都不装也是一个方案，公式可变形为

最终返回结果即为，即得到分数时的方案数

注意:本题最后需要对取模，所以判断最后能否出去玩不能仅仅在最后判断方案数是否等于，需要在计算时就判断是否有方案存在

完整代码

C++

#include <bits/stdc++.h>
using namespace std;
const int mod = 66;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int Test;
    cin >> Test;
    while (Test--) {
        int n, target_points;
        bool flag = false;
        cin >> n >> target_points;
        vector<long long> dp(target_points + 1, 0), p(n);
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
        }
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = target_points; j >= p[i]; --j) {
                dp[j] += dp[j - p[i]];
                if (dp[target_points]) {
                    flag = true;
                }
                if (dp[j] > INT_MAX) {
                    dp[j] %= mod;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = target_points; j >= p[i]; --j) {
                dp[j] += dp[j - p[i]];
                if (dp[target_points]) {
                    flag = true;
                }
                if (dp[j] > INT_MAX) {
                    dp[j] %= mod;
                }
            }
        }
        if (flag) {
            cout << dp[target_points] % mod << endl;
        } else {
            cout << "There's nothing left!" << endl;
        }
    }
    return 0;
}

Python

for _ in range(int(input())):
    n, target_points = map(int, input().split())
    p = list(map(int, input().split()))
    dp = [0 for __ in range(target_points + 1)]
    dp[0] = 1
    flag = False
    for __ in range(2):
        for point in p:
            for i in range(target_points, point - 1, -1):
                dp[i] += dp[i - point]
                if dp[target_points]:
                    flag = True
                if dp[i] > 0x3f3f3f3f:
                    dp[i] %= 66
    if flag:
        print(dp[target_points] % 66)
    else:
        print("There's nothing left!")

G.with me

解题思路

结论

长度为奇数并且全部元素按位异或运算后结果不等于的数组，均可以满足题意

证明

当初始时黑板上所有数字异或结果等于，根据规则轮到Cythia，直接获胜

当初始时黑板上所有数字异或结果不等于：

假设数组长度为偶数且 Cythia 面临失败的状态，即此时她无论擦掉哪一个数字，剩余所有数字异或结果都等于，设数组为，其长度为（为偶数），为此时数组全部元素的异或和，为擦掉后数组全部元素的异或和，则有

此时擦掉后有

由于任何数异或自己都等于，则公式可以变形为

根据假设，无论擦掉哪个数字，最后剩余所有数字异或结果都等于，即对任意的都存在，此时对所有对进行异或后结果也等于，即

将公式代入公式得

整理可得：

根据公式得该数组所有元素异或和为，与假设（Cythia 面临失败）相矛盾，即假设不成立

所以当数组长度为偶数时，Cythia 总能找到并在擦掉这个数字之后剩余的所有数字异或结果不等于，由于两人轮流进行游戏，则双方轮到自己时，数组的长度的奇偶性总是不变的，因为是 Cythia 先手，所以她要么获胜，要么总是可以擦掉一个数字之后剩余的所有数字异或结果不等于，直到最后 InHng 擦掉最后一个数字输掉游戏

同理可得，当数组长度为奇数时，Cythia 在擦掉一个数字之后，留给 InHng 的数组长度必定为偶数，此时 InHng 要么获胜，要么总是可以擦掉一个数字之后剩余的所有数字异或结果不等于，直到最后 Cythia 擦掉最后一个数字输掉游戏

综上所述：长度为奇数的并且全部元素异或结果不等于的数组都可以让 InHng 获胜

完整代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int Test;
    cin >> Test;
    while (Test--) {
        int n, ans = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int l, mid = 0, x;
            cin >> l;
            for (int j = 0; j < l; ++j) {
                cin >> x;
                mid ^= x;
            }
            if (l % 2 and mid) {
                ans = i;
            }
        }
        if (ans) {
            cout << ans << endl;
        } else {
            cout << "There's nothing left!" << endl;
        }
    }
    return 0;
}

Python

from functools import reduce
from operator import xor

for _ in range(int(input())):
    n, ans = int(input()), 0
    for i in range(1, n + 1):
        l = int(input())
        a = list(map(int, input().split()))
        if l % 2 and reduce(xor, a):
            ans = i
    print(ans if ans else "There's nothing left!")

H.寻找好区间

题目大意

给定个长度为的字符串，要求计算出区间内这个字符串的数量大于等于的区间个数。

解题思路

做法：前缀和，二分

对于如何快速求出一个区间内满足条件的字符串的数量，我们可以用前缀和，我们建立一个数组，如果第个字符串是目标字符串，则令，否则令。然后对数组求一遍前缀和，对于区间，区间中满足条件的字符串的数量为。

我们考虑枚举左端点，用二分的方式求出第一个满足的，显然及其右边的点都可作为满足条件的右端点，所以对于此时的，最后的答案应该加上。

注意答案可能会爆，所以要开来记录答案。

时间复杂度

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII; 
const int N=3e5+10;
const int M=2e3+10;
int a[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(s=="byl") a[i]=1;
        else a[i]=0;
        a[i]+=a[i-1];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int l=i,r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(a[mid]-a[i-1]>=k) r=mid-1;
            else l=mid+1;
        }
        ans+=n-l+1;
    }
    cout<<ans;
    return 0;
}

另外，本题还可以使用双指针配合前缀和来处理，这种做法交给读者自己完成，这里就不做展开了。

双指针和前缀和做法的时间复杂度为 。

I.小白的代数题

题目大意

小曾的手上最开始有个糖果，现在有次操作，每次操作能将小曾手上的数变为原来的倍加上个，求每次操作后小曾手上的糖果数之和。

解题思路

做法：推公式，快速幂

分析题意可知，我们可以忽略每次魔法的第二阶段，在每次魔法进行完第一阶段之后，将答案加上此时的糖果数即可。我们设第次魔法后小曾手上的糖果数为，其中，不难看出此题的答案就是从加到的和。根据题意我们可以得到下列式子

对公式进行变形可得

不难看出，当时，数列{}是一个首项为，公比为的等比数列，故根据等比数列的基本公式，有

进而得出的通项公式为

根据等差数列以及等比数列的求和公式可以求出数列的前项和为

故当时，我们只需要输出 这个答案即可。

当时，不难看出是一个等差数列，利用等差数列的求和公式算出答案即可。

本题输出答案需要用到快速幂，时间复杂度为

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod=1e9+7;
int ksm(int a,int b,int c){
    a%=c;
    int ans=1;
    while(b){
        if(b%2) ans=(ans*a)%c;
        a=(a*a)%c;
        b/=2;
    }
    return ans;
}
int Inv(int x){
    return ksm(x,mod-2,mod);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,k,m,t;
    cin>>n>>k>>m>>t;
    int ans;
    if(k==1) ans=(2*n+(t+1)*m%mod)%mod*t%mod*Inv(2)%mod;
    else ans=((ksm(k,t,mod)-1+mod)*(k*n%mod+m+m*Inv(k-1)%mod)%mod*Inv(k-1)%mod-m*t%mod*Inv(k-1)%mod+mod)%mod;
    cout<<ans;
    return 0; 
}

J.小白的几何题

题目大意

本题要在二维平面内构造出一个直角三角形，使其满足以下条件：

此直角三角形的直角边长要为和

此直角三角形的三个顶点坐标都要为绝对值不超过的整数

此直角三角形的三条边都不平行于坐标轴

解题思路

此题的构造方式有多种，下面提供一种可能的构造方式：

我们可以构造一个类似于下图的三角形，其中直角顶点在原点，两条直角边分别在第一象限和第二象限。

我们假设的长度是，的长度是，接下来我们要判断这样的三角形是否存在，我们过点和点作轴的两条垂线，垂足记为，由于三角形的三个点的坐标都要是整数，故边的长度都必须是整数。我们考虑枚举边的长度，枚举范围是从到，进而通过勾股定理求出的长度，如果的长度是整数，我们再根据和的相似关系，有

进而求出和，当和的长度都是整数时，我们最后再特判是否平行于轴，如果此时不平行于轴，那么我们已经成功构造出了一个满足条件的三角形，输出和三点的坐标即可。

如果枚举完的长度之后还没有找到符合条件的三角形，输出即可。

时间复杂度

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int a,b;cin>>a>>b;
    for(int i=1;i<a;i++){
        int num=a*a-i*i;
        int k=sqrt(num);
        if(k*k==num){
            if(b*i%a==0&&b*k%a==0){
                int sx=b*i/a,sy=b*k/a;
                if(i==sy) continue;
                cout<<"YES\n";
                cout<<0<<" "<<0<<"\n";
                cout<<-k<<" "<<i<<"\n";
                cout<<sx<<" "<<sy<<"\n";
                return 0;
            }
        }
    }
    cout<<"NO";
    return 0;
}

K.球包树

题目大意

​给定一棵有个节点的根为树，树中每个点都有一个权值，要求动态的修改树上路径的权值，对子树权值进行修改，查询的值，其中定义为节点到节点路径上点的权值和。

解题思路

​首先我们思考如何计算初始的值，该式实际上要计算的是树中任意两点之间的路径权值的和。直接考虑任意两点之间的路径权值的和是不太好对答案进行计算的，我们可以考虑每个点对答案的贡献是多少。每个点对答案的贡献是什么呢？假设点的权值为,经过该点的路径数量为，那么点对答案的贡献就是。

​那么经过点的路径数量该怎么求呢？其实就是穿过该点的路径数+从该点出发的路径数。从该点出发的路径数恒等于。那穿过点的路径数量是多少呢？假设把点的父节点也当做子节点，那么穿过点 u 的路径其实就是从点的某个儿子节点的子树中选出一个点走向点 u 的另外一个儿子节点的子树节点。定义为点的子树中（包含点）点的数量，假设点的儿子节点为其实是点 u 的父节点，定义，那么经过点的路径数量。所以我们对树跑一遍求出每个点的，然后利用上面的方法就可以求出每个点对答案的贡献。

​所以上面的方法可以在的时间复杂度内求出初始公式的值，下面考虑每次进行树的操作对答案的贡献是多少。我们先定义为经过点的路径数量。

​当为第一种操作时，即 将路径之间点的权值加，定义为点到点路径上点的的和，那么该操作对答案的贡献就是。那么我们如何求呢？我们可以再跑一遍求出每个点到根节点路径上点的的和，将其表示为，再定义表示点和点的最近公共祖先，表示点的父节点，那么。至此，我们便求出了第一种操作对答案的贡献。

​当为第二种操作时，和第一种思路类似，这次定义表示点的子树中所有点的的和。每个点的我们可以通过一次求出来。那么第二次操作对答案的贡献就是。

​当为第三种操作，我们直接输出答案就可以。

该题的时间复杂度为。

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int dep[N],fa[N/2][22];
const int p=1e9+7;
int h[N],e[N],ne[N],a[N],idx,w[N];
int siz[N];
int pre[N];
int val[N];
int n,m;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa1,int depth)
{
	fa[u][0]=fa1;
	dep[u]=depth;
	for(int i=1;i<=21;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	siz[u]=1;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa1) continue;
		dfs(j,u,depth+1);
		siz[u]+=siz[j];
	}
	int sum=0;
	vector<int> v;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa1) continue;
		v.push_back(siz[j]);
	}
	v.push_back(n-siz[u]);
	w[u]=n;
	for(int i=0;i<v.size();i++)
	{
		int x=v[i];
		w[u]=(w[u]+sum*x%p)%p;
		sum+=x;
	}
}
void dfs1(int u,int fa1)
{
	pre[u]=(pre[fa1]+w[u])%p;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa1) continue;
		dfs1(j,u);
	}
}
void dfs2(int u,int fa1)
{
	val[u]=w[u];
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa1) continue;
		dfs2(j,u);
		val[u]=(val[u]+val[j])%p;
	}
}
int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	for(int k=20;k>=0;k--)
	{
		if(dep[fa[a][k]]>=dep[b]) a=fa[a][k];
	} 
	if(a==b) return a;
	for(int k=20;k>=0;k--)
	{
		if(fa[a][k]!=fa[b][k]) 
		{
			a=fa[a][k];
			b=fa[b][k];
		}
	}
	return fa[a][0];
}
void solve()
{
	memset(h,-1,sizeof(h));
	cin >> n >> m;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0,1);
	dfs1(1,0);
	dfs2(1,0);
	int res=0;
	for(int i=1;i<=n;i++) res=(res+w[i]*a[i]%p)%p;
	while(m--)
	{
		int op;
		scanf("%lld",&op);
		if(op==1)
		{
			int u,v,x;
			scanf("%lld%lld%lld",&u,&v,&x);
			int r=lca(u,v);
			int sum=(pre[u]+pre[v]-pre[r]-pre[fa[r][0]])%p+p;
			res=(res+sum*x%p)%p;
		}
		else if(op==2)
		{
			int u,x;
			scanf("%lld%lld",&u,&x);
			res=(res+val[u]*x)%p;
		}
		else printf("%lld\n",res);
	}
}
signed main()
{
	int t;
	t=1;
	solve();
}

L.开心消消乐

题目大意

​ 给定一个长度为的数组，其中第个数字为。每次操作可以从数组中选择一个数删除，数组中被删除数字的倍数以及因子也会被删除，问最少在经过多少次操作，数组变为空？

解题思路

因为当删除某个数字的时候，它的倍数以及因子都会被删除，那么我们很自然的可以想到对于某个数字，若其倍数或者因子也在数组中，我们可以在它们之间连一条边，表示两者是相互依存的。所以我们按照这个思路，最终会形成一个图。且这个图中最多只有个点（因为数组中）。这个图被分成了若干个连通块，对于每一个连通块，若其中一个点被删掉，那么这个连通块中的所有点全部将会被删掉。所以最少操作次数即为图中连通块的数量。

​求图中连通块的数量，很自然可以想到使用并查集来写。那么这里建图就有两种方式，第一种是根据将每个点与其因子相连的方式建图，第二种是根据将每个点与其倍数相连的方式建图。前者建图是的时间复杂度，后者是的时间复杂度。

完整代码

时间复杂度为的方式：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int a[N];
int p[N];
int cnt[N];
int find(int x)
{
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
void solve()
{
	int n;
	cin >> n;
	for(int i=1;i<=100000;i++) p[i]=i;
	set<int> s;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		s.insert(a[i]);
		cnt[a[i]]++;
	}
	for(auto it:s) cnt[it]++;
	for(auto it:s)
	{
		for(int i=1;i<=it/i;i++)
		{
			if(it%i==0)
			{
				if(cnt[i])
				{
					if(find(i)!=find(it))
					{
						p[find(it)]=find(i);
					}
				}
				if(cnt[it/i])
				{
					if(find(it/i)!=find(it))
					{
						p[find(it)]=find(it/i);
					}
				}
			}
		}
	}
	set<int> s1;
	for(auto it:s) s1.insert(find(it));
	printf("%lld\n",s1.size());
}
signed main()
{
	int t;
	t=1;
//	cin >> t; 
	while(t--) solve();
} 

时间复杂度为的方式：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int a[N];
int p[N];
int cnt[N];
int find(int x)
{
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
void solve()
{
	int n;
	cin >> n;
	for(int i=1;i<=100000;i++) p[i]=i;
	set<int> s;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		s.insert(a[i]);
		cnt[a[i]]++;
	}
	for(auto it:s) cnt[it]++;
	for(auto it:s)
	{
		for(int i=1;i*it<=100000;i++)
		{
			if(cnt[i*it])
			{
				int x=i*it;
				if(find(x)!=find(it))
				{
					p[find(it)]=find(x);
				}
			}
		}
	}
	set<int> s1;
	for(auto it:s) s1.insert(find(it));
	printf("%lld\n",s1.size());
}
signed main()
{
	int t;
	t=1;
//	cin >> t; 
	while(t--) solve();
}