結果

問題 No.1494 LCS on Tree
コンテスト
ユーザー southsidesamurai65-prog
提出日時 2026-08-24 21:47:02
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 48 ms / 2,000 ms
+ 938µs
コード長 1,889 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,333 ms
コンパイル使用メモリ 186,104 KB
実行使用メモリ 35,072 KB
最終ジャッジ日時 2026-08-24 21:47:17
合計ジャッジ時間 7,904 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<string>
#include<vector>
using namespace std;
typedef pair<int,char> pic;
int main(){
    int n;cin>>n;
    string s;cin>>s;int m=s.size();
    s='x'+s; //挪到1-base
    vector<vector<pic>> g(n+1);
    int u,v;char c;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v>>c;
        g[u].push_back(make_pair(v,c));
        g[v].push_back(make_pair(u,c));
    }
    u=1;
    vector<int> p(n+1,-2);
    vector<int> ngb(n+1,0);
    vector<vector<int>> up(n+1,vector<int>(m+1,0));
    vector<vector<int>> down(n+1,vector<int>(m+1,0));
    vector<char> pth(n+1);
    p[u]=-1;
    int ans=0;
    while(true){
        if(ngb[u]<g[u].size()){
            auto vc=g[u][ngb[u]++];
            v=vc.first;c=vc.second;
            if(p[v]!=-2) continue;
            p[v]=u;
            pth[v]=c;
            u=v;
        }else{
            //用到父亲的字符更新up和down
            if(p[u]==-1) break;
            v=p[u];
            //首先更新down[u][i]和up[u][i]
            auto old=up[u];
            up[u][0]=0;
            for(int i=1;i<=m;i++){
                if(pth[u]==s[i]) up[u][i]=1+old[i-1];
                else{
                    up[u][i]=max(up[u][i-1],old[i]);
                }
            }
            old=down[u];
            down[u][0]=0;
            for(int i=1;i<=m;i++){
                if(pth[u]==s[m-i+1]) down[u][i]=1+old[i-1];
                else down[u][i]=max(down[u][i-1],old[i]);
            }
            //更新答案
            for(int i=0;i<=m;i++){
                ans=max(ans,up[v][i]+down[u][m-i]);
                ans=max(ans,down[v][i]+up[u][m-i]);
            }
            //更新父节点
            for(int i=0;i<=m;i++){
                up[v][i]=max(up[v][i],up[u][i]);
                down[v][i]=max(down[v][i],down[u][i]);
            }
            u=v;
        }
    }
    cout<<ans<<endl;
    return 0;
}
0