CFR 615 B. Longtail Hedgehog ( DP )

Problem - 615B - Codeforces
題意：
給一張不一定連通的圖。求一個序列，使起點至終點都相鄰，且編號遞增，此前提下序列長度和序列末尾節點的度數之乘積最大。
解法：
dp[ i ] : 以 i 節點為末尾的最長序列長度
更新方向顯然是由編號小的節點至大的就行了。

int N, M;
vvi G;

void init(){
    cin >> N >> M;
    G = vvi( N );
    for( int i = 0; i < M; ++i ){
        int u, v; cin >> u >> v;
        if( not ( u < v ) )
            swap( u, v );
        G[ u - 1 ].emplace_back( v - 1 );
    }
}

vi dp;
vi deg;

void preprocess(){
    dp = vi( N, 1 );
    for( int i = 0; i < N; ++i )
        for( int v : G[ i ] )
            upmax( dp[ v ], dp[ i ] + 1 );
    deg = vi( N );
    for( int i = 0; i < N; ++i )
        for( int v : G[ i ] )
            ++deg[ i ],
            ++deg[ v ];
}

void solve(){
    ll ans = 0;
    for( int i = 0; i < N; ++i )
        upmax( ans, 1LL * dp[ i ] * deg[ i ] );
    cout << ans << endl;
}