列表

详情

NC213912. 芭芭拉冲鸭~（续）

描述

芭芭拉这次来到了一棵字母树，这同样是一棵无根树，每个节点上面有一个小写字母。
芭芭拉想知道，自己从x冲刺到y，从x走到y收集所有字母，选择其中一部分字母组成一个回文串，这个回文串的最大长度是多少？
同样的，芭芭拉冲刺的时候是不能掉头的。
一共有q次询问。每次的询问是独立的（即本次收集字母不影响之后的询问，每次询问时字母都是未被收集状态）。

输入描述

第一行有一个正整数。 
接下来的行，每行输入两个正整数和，代表和之间有一条无向边相连。 
接下来一行有一个长度为的字符串，字符串仅由小写字母构成。第个字符表示节点上的字母。 
接下来一行是一个正整数，代表询问次数。 
接下来的行，每行两个正整数和。 
（保证输入一定是一棵树）


输出描述

对应每次询问，输出一个正整数，代表回文串的最大长度。

示例1

输入: 

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

输出: 

3
1
1

说明:

这棵树的构造如下：

对于第一个询问，芭芭拉冲刺的路径是4-2-5，收集的字母有两个b一个a，可以构建的最长回文串是"bab"，长度为3。
对于第二个询问，芭芭拉冲刺的路径是1-2，收集的字母有一个b一个a，可以构建的最长回文串是"a"（也可以是"b"），长度为1。
对于第三个询问，芭芭拉起点和终点都是3，所以站在原地不动，收集的字母有只有一个c，可以构建的最长回文串是"c"，长度为1。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 126ms, 内存消耗: 18868K, 提交时间: 2020-11-21 16:09:36 

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,s[N],f[N][20],dep[N]; char str[N];
vector<int> g[N];
void dfs(int x,int fa){
	s[x]=s[fa]^(1<<(str[x]-'a')); 
	dep[x]=dep[fa]+1; f[x][0]=fa;
	for(int i=1;i<=17;i++) f[x][i]=f[f[x][i-1]][i-1];
	for(int to:g[x]) if(to!=fa) dfs(to,x);
}
inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=17;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=17;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
signed main(){
	cin>>n;
	for(int i=1,a,b;i<n;i++) scanf("%d %d",&a,&b),g[a].push_back(b),g[b].push_back(a);
	scanf("%s",str+1); dfs(1,0); cin>>q;
	for(int i=1,x,y,lc,cnt,dis;i<=q;i++){
		scanf("%d %d",&x,&y);
		lc=lca(x,y); cnt=0; dis=dep[x]+dep[y]-2*dep[lc]+1;
		for(int j=0;j<26;j++){
			int k=(s[x]>>j&1)^(s[y]>>j&1);
			if(str[lc]-'a'==j) k^=1;
			if(k) cnt++;
		}
		if(cnt>1) printf("%d\n",dis-cnt+1);
		else printf("%d\n",dis);
	}
	return 0;
}

上一题

© 2025 nowcoder.com