結果

問題 No.1494 LCS on Tree
ユーザー sapphire__15sapphire__15
提出日時 2021-04-30 23:33:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 197 ms / 2,000 ms
コード長 3,898 bytes
コンパイル時間 1,428 ms
コンパイル使用メモリ 134,728 KB
最終ジャッジ日時 2025-01-21 04:46:36
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <functional>
#include <cassert>
#include <stack>
#include <numeric>
#include <iomanip>
#include <limits>
#include <random>
#include <unordered_map>

typedef int64_t ll;
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> Pdd;

#define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++)
#define all(_l) _l.begin(), _l.end()
#define rall(_l) _l.rbegin(), _l.rend()
#define MM << " " <<

template<typename _T>
using MaxHeap = std::priority_queue<_T>;
template<typename _T>
using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>;

template<typename _T>
inline bool chmax(_T &_l, const _T _b) {
    if (_l < _b) {
        _l = _b;
        return true;
    }
    return false;
}
template<typename _T>
inline bool chmin(_T &_l, const _T _b) {
    if (_l > _b) {
        _l = _b;
        return true;
    }
    return false;
}

template<typename _T>
void vdeb(const std::vector<_T> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        if (i == bb.size() - 1) std::cout << bb[i];
        else std::cout << bb[i] << ' ';
    }
    std::cout << '\n';
}
template<typename _T>
void vdeb(const std::vector<std::vector<_T>> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        // std::cout << i << ' ';
        vdeb(bb[i]);
    }
    std::cout << '\n';
}

using namespace std;

int N;
string s;

struct Edge {
    int to;
    char c;
    Edge() {}
    Edge(int _to, char _c) : to(_to),c(_c) {}
};

struct DP {
    int n;
    vector<int> dp;
    // DP() {}
    DP(int _n = s.size()) : n(_n), dp(n) {}
    DP addroot(char c) {
        DP ret(*this);
        rip(i,n,0) {
            if(i) ret.dp[i] = max(max(ret.dp[i-1], dp[i]), dp[i-1] + ((s[i] == c) ? 1 : 0));
            else ret.dp[i] = max((s[i] == c) ? 1 : 0, dp[i]);
        }
        return ret;
    }
    DP& operator+=(const DP &other) {
        rip(i,n,0) chmax(dp[i], other.dp[i]);
        return *this;
    }
    DP operator+(const DP &other) {
        DP ret(*this);
        rip(i,n,0) chmax(ret.dp[i], other.dp[i]);
        return ret;
    }
};

void dfs1(vector<vector<Edge>> &da, vector<DP> &dp, int pare = -1, int child = 0) {
    for(int i = 0; i < int(da[child].size()); i++){
        if(da[child][i].to == pare) continue;
        dfs1(da, dp, child, da[child][i].to);
        dp[child] += dp[da[child][i].to].addroot(da[child][i].c);
    }
}

void dfs2(vector<vector<Edge>> &da, vector<DP> &ans, const DP &dp = DP(), int pare = -1, int child = 0){
    if(pare != -1) ans[child] += dp;
    int size = da[child].size();
    vector<DP> dpL(size+1) ,dpR(size+1);
    for(int i = 0;i < size; i++){
        int next = da[child][i].to;
        dpL[i+1] = dpL[i];
        if(next == pare) dpL[i+1] += dp;
        else dpL[i+1] += ans[next].addroot(da[child][i].c);
    }
    for(int i = size; i > 0; i--){
        int next = da[child][i-1].to;
        dpR[i-1] = dpR[i];
        if(next == pare) dpR[i-1] += dp;
        else dpR[i-1] +=  ans[next].addroot(da[child][i-1].c);
    }
    for(int i = 0;i < size;i++){
        int next = da[child][i].to;
        if(next == pare) continue;
        dfs2(da, ans, (dpL[i] + dpR[i+1]).addroot(da[child][i].c), child, next);
    }
}

void rooting(vector<vector<Edge>> &da, vector<DP> &dp) {
    dfs1(da, dp);
    dfs2(da, dp);
}

int main() {
    cin >> N;
    cin >> s;
    vector<vector<Edge>> da(N, vector<Edge>(0));
    rip(i,N-1,0) {
        int x, y; cin >> x >> y;
        char c; cin >> c;
        --x; --y;
        da[y].push_back({x, c});
        da[x].push_back({y, c});
    }
    vector<DP> dp(N, s.size());
    rooting(da, dp);
    int ans = 0;
    rip(i,N,0) {
        chmax(ans, dp[i].dp.back());
    }
    cout << ans << endl;
}
0