2.11学习总结

有效点对https://www.acwing.com/problem/content/description/5472/

给定一个 n� 个节点的无向树，节点编号 1∼n1∼�。

树上有两个不同的特殊点 x,y�,�，对于树中的每一个点对 (u,v)(u≠v)(�,�)(�≠�)，如果从 u� 到 v� 的最短路径需要经过点 x� 和点 y�（路径的两个端点也算经过），且相对顺序上先经过点 x�，后经过点 y�，那么就称 (u,v)(�,�) 是一个无效点对，否则就称 (u,v)(�,�) 是一个有效点对。

请你计算树中有效点对的数量。

注意：

1. (u,v)(�,�) 和 (v,u)(�,�) 是两个不同的点对。
2. 有效点对必须满足 u≠v�≠�。

输入格式

第一行包含三个整数 n,x,y�,�,�。

接下来 n−1�−1 行，每行包含两个整数 a,b�,�，表示点 a� 和点 b� 之间存在一条无向边。

输出格式

一个整数，表示有效点对的数量。

数据范围

前 33 个测试点满足 1≤n≤101≤�≤10。
所有测试点满足 1≤n≤3×1051≤�≤3×105，1≤x,y≤n1≤�,�≤�，x≠y�≠�，1≤a,b≤n1≤�,�≤�，a≠b�≠�。

输入样例1：

3 1 3
1 2
2 3

输出样例1：

5

输入样例2：

3 1 3
1 2
1 3

输出样例2：

4

思路：用DFS，只要计算出无效点，就可以得到有效点的数量，由于是树状结构，所以x点y的路径总和等于以x为根的子树大小*以y为根的子树大小

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=3e5+5;
int dp[N],vis[N];
vector<int>e[N];
void dfs(int u,int fa){
	dp[u]=1;
	for (int i=0;i<e[u].size();++i){
		int v=e[u][i];
		//if (vis[v]) continue;
		if (v!=fa){
			//vis[v]=1;
			dfs(v,u);
			dp[u]+=dp[v];
			//vis[v]=0;
		}
	}
}
signed main(){
	int n,x,y;
	cin>>n>>x>>y;
	for (int i=0;i<n-1;++i){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(y,-1);
	int res=dp[x];
	for (int i=1;i<=n;++i) dp[i]=0;
	dfs(x,-1);
	res=dp[y]*res;
	res=n*(n-1)-res;
	cout<<res;
} 

最有价值字符串https://www.acwing.com/problem/content/description/5471/

A,B,C�,�,� 三人在玩一个有关字符串的游戏。

给定三人每人一个由大小写字母构成的字符串。

三人的字符串的长度相同。

规定，一个字符串的价值等于该字符串中出现次数最多的子串的出现次数。

例如，aaaaaa 的价值为 66，因为出现次数最多的子串 a 一共出现了 66 次；abab 的价值为 22，因为出现次数最多的子串 ab 一共出现了 22 次。

游戏开始后，每人都需要对自己的字符串进行恰好 n� 次修改，每次修改需要将字符串中的某个字符修改为另一个不同的字符，例如将 aaab 修改为 acab。

所有修改完毕后，最有价值字符串的拥有者将获得游戏胜利。

请你计算，如果所有人都采取最优策略，那么谁将最终获胜。

输入格式

第一行包含整数 n�。

第二行，包含一个由大小写字母构成的字符串，表示给 A� 的字符串。

第三行，包含一个由大小写字母构成的字符串，表示给 B� 的字符串。

第四行，包含一个由大小写字母构成的字符串，表示给 C� 的字符串。

保证这三个人获得的字符串的长度均相同。

输出格式

共一行，A� 获胜则输出 A，B� 获胜则输出 B，C� 获胜则输出 C，不止一人获胜则输出 D。

数据范围

前 66 个测试点满足 0≤n≤200≤�≤20，每个输入字符串的长度范围 [1,20][1,20]。
所有测试点满足 0≤n≤1090≤�≤109，每个输入字符串的长度范围 [1,105][1,105]。

输入样例1：

3
abcdd
efgcd
hijgk

输出样例1：

A

输入样例2：

7
abcdefbcgfhi
igbccjbkchle
gkmnlcjnboce

输出样例2：

B

输入样例3：

1
abcabc
cbabac
ababca

输出样例3：

C

输入样例4：

15
abcdefghi
jkdlbmnop
jqrstduve

输出样例4：

D

思路：先算出单个字符的最大价值，然后找到可更换的数量，和需要更换的次数，如果可更换的次数为0且需要更换次数为1，那么总数减1，否则，就是加上min（可更换次数，需要更换次数），如果可更换次数更大，那么所有需要更换次数都用在更换字符上，反之就是把可更换的字符都更换了

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
map<char,int>ma,mb,mc;
signed main(){
	int n;
	cin>>n;
	string a,b,c;
	cin>>a>>b>>c;
	int man=0,mbn=0,mcn=0;
	for (int i=0;i<a.size();++i){
		ma[a[i]]++;
		mb[b[i]]++;
		mc[c[i]]++;
		man=max(man,ma[a[i]]);
		mbn=max(mbn,mb[b[i]]);
		mcn=max(mcn,mc[c[i]]);
	}
	//找到可以交换的个数来提高价值
	int ka=0,kb=0,kc=0;
	ka=a.size()-man;
	kb=a.size()-mbn;
	kc=a.size()-mcn;
	//aaaaaaa  ma=5 ka=0 n=3
	if (!ka && n==1) man=a.size()-1;
	else man+=min(ka,n);
	if (!kb && n==1) mbn=a.size()-1;
	else mbn+=min(kb,n);
	if (!kc&& n==1) mcn=a.size()-1;
	else mcn+=min(kc,n);
	if (man>mbn && man>mcn) cout<<"A";
	else if (mbn>man && mbn>mcn) cout<<"B";
	else if (mcn>man && mcn>mbn) cout<<"C";
	else  cout<<"D";
	
} 

大臣的旅费https://www.luogu.com.cn/problem/P8602

题目描述

很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 �x 千米到第 �+1x+1 千米这一千米中（�x 是整数），他花费的路费是 �+10x+10 这么多。也就是说走 11 千米花费 1111，走 22 千米要花费 2323。

J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数 �(�≤105)n(n≤105)，表示包括首都在内的 �T 王国的城市数。

城市从 11 开始依次编号，11 号城市为首都。

接下来 �−1n−1 行，描述 �T 国的高速路（�T 国的高速路一定是 �−1n−1 条）。

每行三个整数 ��,�,��Pi​,Q,Di​，表示城市 ��Pi​ 和城市 ��Qi​ 之间有一条高速路，长度为 ��(��≤1000)Di​(Di​≤1000) 米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

输入输出样例

输入 #1复制

5
1 2 2
1 3 1
2 4 5
2 5 4

输出 #1复制

135

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
int f[500005],vis[500005],dp[500005];
struct edge{
	int to;
	int w;
	edge(int a,int b){
		to=a;
		w=b;
	}
};
vector<edge>tree[500005];
void dfs(int u){
	vis[u]=1;
	for (int i=0;i<tree[u].size();++i){
		edge y=tree[u][i];
		if (vis[y.to])continue;
		dfs(y.to);
		f[u]=max(f[u],dp[u]+dp[y.to]+y.w);
		dp[u]=max(dp[u],dp[y.to]+y.w);
	}
	return ;
}
signed main(){
	int n; cin>>n;
	for (int i=0;i<n-1;++i){
		int u,v,w;
		cin>>u>>v>>w;
		tree[u].push_back(edge(v,w));
		tree[v].push_back(edge(u,w));
	}
	dfs(1);
	int res=f[1];
	for(int i=2;i<=n;++i){
		res=max(res,f[i]);
	} 
	cout<<res*10+res*(res+1)/2;
}

树的直径https://www.luogu.com.cn/problem/U81904

题目描述

给定一棵树，树中每条边都有一个权值，

树中两点之间的距离定义为连接两点的路径边权之和。

树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。

现在让你求出树的最长链的距离

输入格式

给定一棵无根树

第一行为一个正整数�n,表示这颗树有�n个节点

接下来的�−1n−1行,每行三个正整数�,�,�u,v,w，表示�,�u,v（�,�<=�u,v<=n）有一条权值为�w的边相连

数据保证没有重边或自环

输出格式

输入仅一行，表示树的最长链的距离

输入输出样例

输入 #1复制

6
1 2 1
1 3 2
2 4 3
4 5 1
3 6 2

输出 #1复制

9

说明/提示

对于1010的数据 �<=10n<=10

对于3030的数据 �<=1000n<=1000

对于5050的数据 �<=10000n<=10000

对于7070的数据 �<=100000n<=100000 边权均为正整数

对于100100的数据 �<=500000n<=500000 边权可能为负

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
int f[500005],vis[500005],dp[500005];
struct edge{
	int to;
	int w;
	edge(int a,int b){
		to=a;
		w=b;
	}
};
vector<edge>tree[500005];
void dfs(int u){
	vis[u]=1;
	for (int i=0;i<tree[u].size();++i){
		edge y=tree[u][i];
		if (vis[y.to])continue;
		dfs(y.to);
		f[u]=max(f[u],dp[u]+dp[y.to]+y.w);
		dp[u]=max(dp[u],dp[y.to]+y.w);
	}
	return ;
}
signed main(){
	int n; cin>>n;
	for (int i=0;i<n-1;++i){
		int u,v,w;
		cin>>u>>v>>w;
		tree[u].push_back(edge(v,w));
		tree[v].push_back(edge(u,w));
	}
	dfs(1);
	int res=f[1];
	for (int i=2;i<=n;++i){
		res=max(res,f[i]);
	}
	cout<<res;
}