2 条题解

  • 0
    @ 2026-5-27 12:16:07 
    #include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
const int N=5e4+10,B=131,P=998244353;
int fac[N];map<int,int>mp[N];char st[N];
int siz[N],d[N],d1[N],del[N],all,cnt,rt,rtmx,n,k,bk;
vector<int>G[N];
void getrt(int x,int f)
{
	siz[x]=1;int mx=0;
	for(int y:G[x])if(!del[y]&&y!=f)
	{
		getrt(y,x);
		siz[x]+=siz[y];
		mx=max(mx,siz[y]);
	}
	mx=max(mx,all-siz[x]);
	if(mx<rtmx)rtmx=mx,rt=x;
}
void getdis(int x,int f,int s,int t,int dep)
{
	if(dep<=k)d[++cnt]=((s-t*fac[k-dep])%P+P)%P,d1[cnt]=dep;
	else return;
	for(int y:G[x])if(!del[y]&&y!=f)
		getdis(y,x,(s*B+st[y])%P,(t+st[y]*fac[dep])%P,dep+1);
}
void getdis1(int x,int f,int s,int t,int dep)
{
	int ps=(s*B+st[x])%P,pt=(t+st[x]*fac[dep])%P;
	if(dep==k-1&&ps==pt){bk=1;return;}
	if(dep<=k-1)d[++cnt]=((ps-pt*fac[k-dep-1])%P+P)%P,d1[cnt]=dep+1;
	else return ;
	for(int y:G[x])if(!del[y]&&y!=f)
		getdis1(y,x,ps,pt,dep+1);
}
void calc(int x)
{
	cnt=0;
	for(int y:G[x])if(!del[y])
	{
		int lst=cnt;
		getdis(y,x,st[y],st[y],1);
		for(int i=lst+1;i<=cnt;i++)if(d1[i]<=k)
			bk|=mp[k-d1[i]][d[i]];
		cnt=lst;
		getdis1(y,x,st[x],st[x],1);
		if(bk)return;
		for(int i=lst+1;i<=cnt;i++)if(d1[i]<=k)
			mp[d1[i]][d[i]]=1;
	}
	for(int i=1;i<=cnt;i++)if(d1[i]<=k)mp[d1[i]].clear();
}
void divide(int x)
{
	del[x]=1;calc(x);
	if(bk)return;
	for(int y:G[x])if(!del[y])
	{
		if(siz[y]<k)continue;
		all=rtmx=siz[y];getrt(y,0);
		divide(rt);
	}
}
bool check(int x)
{
	if(x==0||x==1)return 1;
	k=x;bk=0;memset(del,0,sizeof(del));
	all=rtmx=n;getrt(1,0);
	getrt(rt,0);
	divide(rt);
	return bk;
}
signed main()
{
	cin>>n;scanf("%s",st+1);
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*B%P;
	for(int i=1;i<n;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int ans=0;
	int l=0,r=n/2,res=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid*2))l=mid+1,res=mid;
		else r=mid-1;
	}
	ans=max(ans,res*2);
	l=0,r=(n-1)/2,res=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(r*2+1<ans)break;
		if(check(mid*2+1))l=mid+1,res=mid;
		else r=mid-1;
	}
	ans=max(ans,res*2+1);
	cout<<ans;
	return 0;
}
    • 0
      @ 2026-4-29 21:46:28

      题意

      一棵树，每个结点有一个小写字母，求最长的回文路径。

      思路

      路径问题我们可以想到用点分治来求解。

      我们点分治的时候，维护每个点到重心的正反路径的 hash 值。

      设点到重心的 hash 值为 AA，重心到点的 hash 值为 BB。

      假设实现我们有两个长度分别为 L1,L2L_1,L_2 的路径，它们的 LCA 是当前分治到的重心。

      这两条路径要组成回文路径当且仅当：

      A1+B2×27L1=A2+B1×27L2A_1+B_2\times 27^{L_1}=A_2+B_1\times 27^{L_2}

      移项，同除 27L1+L227^{L_1+L_2}：

      $$A_1/27^{L_1+L_2}-B_1/ 27^{L_1}=A_2/27^{L_1+L_2}-B_2/ 27^{L_2}$$

      这里 L1+L2L_1+L_2 就是回文路径的长度。

      我们知道，一个路径如果是回文路径，那么去掉头尾两个结点它仍然是回文路径。

      我们考虑奇偶长度分开来二分，然后每次做点分治，并记录下 A/27len−B/27LA/27^{len}-B/ 27^{L}。

      时间复杂度为 O(nlog⁡3n)O(n\log^3n)，需要卡常。

      一个卡常技巧就是，如果 分治到的联通块大小 小于 固定的回文路径长度 时，就直接返回。

      记录时将 map 换成 unordered_map 实测快不少。

      代码

      #include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<set>
#include<bitset>
#define LL long long
using namespace std;
namespace MOD
{
    const int mod = 1e9 + 7;
    inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
    inline int mul(int a, int b) {return 1ll * a * b % mod;}
    inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
    inline int fast_pow(int a, int b)
    {
        int re = 1;
        while(b)
        {
            if(b & 1) re = mul(re, a);
            a = mul(a, a);
            b >>= 1;
        }
        return re;
    }
    inline int inv(int a) {return fast_pow(a, mod - 2);}
} using namespace MOD;
int n, ans = 1, p[50005], invp[50005]; char c[50005];
struct Node
{
    int to, nxt;
}r[100005]; int he[50005];
inline void Edge_add(int u, int v)
{
    static int cnt = 0;
    r[++cnt] = (Node){v, he[u]};
    he[u] = cnt;
}
bitset<50005> vis;
int tot, sz[50005], Mx[50005], rt;
void getrt(int now, int fa)
{
    sz[now] = 1, Mx[now] = 0;
    for(int i = he[now]; i; i = r[i].nxt)
    {
        int to = r[i].to;
        if(vis[to] || to == fa) continue;
        getrt(to, now);
        sz[now] += sz[to];
        Mx[now] = max(Mx[now], sz[to]);
    }
    Mx[now] = max(Mx[now], tot - sz[now]);
    if(Mx[now] < Mx[rt]) rt = now;
}
int h1[50005], h2[50005], dep[50005], q[50005], ta, nlen;
int L, R; bool chk;
#define pii pair<int, int>
#define mp make_pair
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 
unordered_map<pii, bool, hash_pair> f;
inline void gethash(int now, int fa)
{
    for(int i = he[now]; i; i = r[i].nxt)
    {
        int to = r[i].to;
        if(vis[to] || to == fa) continue;
        h1[to] = add(mul(h1[now], 27), c[to] - 'a' + 1), h2[to] = add(h2[now], mul(c[to]- 'a' + 1, p[dep[to] = dep[now] + 1]));
        q[++ta] = to;
        gethash(to, now);
    }
}
#define h(H1, H2, sum, len) sub(mul(H1, invp[sum]), mul(H2, invp[len]))
inline void calc(int now)
{
    f.clear();
    h1[now] = h2[now] = c[now] - 'a' + 1, dep[now] = 0;
    f[mp(0, 0)] = 1;
    for(int i = he[now]; i; i = r[i].nxt)
    {
        int to = r[i].to;
        if(vis[to]) continue;
        h1[to] = add(c[to] - 'a' + 1, h1[now] * 27); h2[to] = add(h2[now], (c[to] - 'a' + 1) * 27), dep[to] = 1;
        q[ta = 1] = to;
        gethash(to, now);
        for(int j = 1; j <= ta; j++)
        {
            int val = h(h1[q[j]], h2[q[j]], nlen, dep[q[j]] + 1);
            if(f[mp(val, nlen - dep[q[j]] - 1)])
                {chk = true; return;}
        }
        for(int j = 1; j <= ta; j++)
        {
            int H1 = sub(h1[q[j]], mul(h1[now], p[dep[q[j]]]));
            int H2 = mul(sub(h2[q[j]], h1[now]), invp[1]);
            int val = h(H1, H2, nlen, dep[q[j]]);
            f[mp(val, dep[q[j]])] = 1;
        }
    }
}
void solve(int now)
{
    vis[now] = 1, calc(now); if(chk) return;
    int rp = tot - sz[now];
    for(int i = he[now]; i; i = r[i].nxt)
    {
        int to = r[i].to;
        if(vis[to]) continue;
        tot = Mx[rt = 0] = (sz[to] > sz[now] ? rp : sz[to]);
        if(tot < nlen) continue;
        getrt(to, 0);
        solve(rt);
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    scanf("%d%s", &n, c + 1);
    p[0] = invp[0] = 1; for(int i = 1; i <= n; i++) p[i] = mul(p[i - 1], 27);
    invp[n] = inv(p[n]); for(int i = n - 1; i >= 1; i--) invp[i] = mul(invp[i + 1], 27);
    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        Edge_add(u, v), Edge_add(v, u);
    }
    L = 1, R = (n + 3) >> 1;
    while(L + 1 < R)
    {
        int mid = (L + R) >> 1;
        vis = chk = 0; nlen = (mid << 1) - 1;
        tot = Mx[rt = 0] = n;
        getrt(1, 0);
        solve(rt);
        if(chk) L = mid;
        else R = mid;
    }
    ans = max(ans, (L << 1) - 1);
    L = ans >> 1, R = (n + 2) >> 1;
    while(L + 1 < R)
    {
        int mid = (L + R) >> 1;
        vis = chk = 0; nlen = mid << 1;
        tot = Mx[rt = 0] = n;
        getrt(1, 0);
        solve(rt);
        if(chk) L = mid;
        else R = mid;
    }
    ans = max(ans, L << 1);
    printf("%d", ans);
    return 0;
}
      • 1

      [COCI 2019/2020 #3] Lampice

      信息

      ID
      10830
      时间
      2500ms
      内存
      256MiB
      难度
      9
      标签
      递交数
      46
      已通过
      3
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 52ms
      4. Powered by Hydro v5.0.1 Community