結果
問題 | No.1494 LCS on Tree |
ユーザー |
![]() |
提出日時 | 2021-04-03 05:37:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,741 bytes |
コンパイル時間 | 2,415 ms |
コンパイル使用メモリ | 212,232 KB |
最終ジャッジ日時 | 2025-01-20 10:19:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
#include<bits/stdc++.h> using std::cin; using std::cout; using std::endl; using ll = long long; using std::vector; using std::string; #define rep(i, j, n) for(int i = int(j); i < int(n); i++) #define REP(i, j, n) for(int i = int(j); i <= int(n); i++) #define per(i, j, n) for(int i = int(j); int(n) <= i; i--) ll N, M; string S; vector<vector<ll>> edge, dp, rev; vector<vector<char>> c; vector<bool> flag; ll ans = 0; void dfs(ll now){ flag[now] = true; rep(i,0,edge[now].size()){ ll next = edge[now][i]; ll ch = c[now][i]; if(flag[next]) continue; dfs(next); per(j,M,1){ dp[next][j] = std::max(dp[next][j], dp[next][j-1]+(S[j-1]==ch)); } REP(j,1,M){ dp[next][j] = std::max(dp[next][j], dp[next][j-1]); } REP(j,1,M){ rev[next][j-1] = std::max(rev[next][j-1], rev[next][j]+(S[j-1]==ch)); } per(j,M,1){ rev[next][j-1] = std::max(rev[next][j-1], rev[next][j]); } REP(j,0,M){ ans = std::max(ans, dp[now][j]+rev[next][j]); ans = std::max(ans, dp[next][j]+rev[now][j]); } REP(j,0,M){ dp[now][j] = std::max(dp[now][j], dp[next][j]); rev[now][j] = std::max(rev[now][j], rev[next][j]); } } } int main(){ cin >> N >> S; M = S.size(); edge.resize(N); c.resize(N); rep(i,1,N){ ll u, v; char c_; cin >> u >> v >> c_; edge[--u].push_back(--v); edge[v].push_back(u); c[u].push_back(c_); c[v].push_back(c_); } dp.resize(N, vector<ll>(M+1)); rev.resize(N, vector<ll>(M+1)); flag.resize(N); dfs(0); cout << ans << endl; }