ABC394E

给定一个$n$个点的有向图的邻接矩阵，每条边的边权是一个小写字符。求任意两点之间的最短回文路径。

考虑多源搜索,令$di{s}_{i,j}$表示$i$到$j$的最短回文路径。枚举扩展点$u$,$v$。如果两边都是相同字符那么可以扩展，$di{s}_{u,v}=di{s}_{i,j}+2$。

一开始把所有形成回文的边入队开始搜索即可。（所有点对$(i,i)$,以及满足$s_{i,j}!{=}^{\prime }{-}^{\prime }$的点对）

每个点对$(i,j)$至多入队搜索一次，每次搜索枚举扩展点$(u,v)$共$n^2$对，总复杂度$O(n^4)$。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 1000005,inf = 2e18,mod=1000000007;
int n;
string s[105];
int dis[105][105];
bool ck(int st,int x,int y,int ed){return s[st][x]==s[y][ed]&&s[st][x]!='-';
}
void solve(){cin>>n;memset(dis,0x3f,sizeof dis);queue<pii>q;for(int i=1;i<=n;i++){cin>>s[i];s[i]=" "+s[i];for(int j=1;j<=n;j++){if(s[i][j]!='-'){dis[i][j]=1;q.push({i,j});}}dis[i][i]=0;q.push({i,i});}while(q.size()){auto [x,y]=q.front();q.pop();for(int u=1;u<=n;u++){for(int v=1;v<=n;v++){if(ck(u,x,y,v)&&dis[u][v]>dis[x][y]+2){dis[u][v]=dis[x][y]+2;q.push({u,v});}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<(dis[i][j]>inf?-1:dis[i][j])<<" \n"[j==n];}}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

ABC394F

给定一个树，找到一个最大的只存在度为$1$和$4$的节点的子树。

考虑类似树的直径做法，令$m{x}_u$表示$u$能够提供给父亲的最大子树大小。转移是最大的三个儿子的$m{x}_v$之和$+1$。

考虑枚举每个点作为度为$4$的节点，接的四个节点一定是最大的四个儿子或者最大的三个儿子加父亲，取最大值就好。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 1000005,inf = 2e18,mod=1000000007;
int n,ans;
vector<int>p[200005];
int mx[2000005];
void dfs(int u,int fa){mx[u]=1;vector<int>a;for(auto v:p[u]){if(v==fa)continue;dfs(v,u);a.push_back(mx[v]);}sort(a.begin(),a.end());reverse(a.begin(),a.end());if(a.size()>=3&&fa){ans=max(ans,a[0]+a[1]+a[2]+1);mx[u]=a[0]+a[1]+a[2]+1;}if(a.size()>=4){ans=max(ans,a[0]+a[1]+a[2]+a[3]+1);}
}
void solve(){cin>>n;ans=-1;for(int i=1;i<n;i++){int u,v;cin>>u>>v;p[u].push_back(v);p[v].push_back(u);}dfs(1,0);cout<<ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}