Alex decided to go on a touristic trip over the country.

For simplicity let's assume that the country has 𝑛 cities and 𝑚 bidirectional roads connecting them. Alex lives in city 𝑠 and initially located in it. To compare different cities Alex assigned each city a score 𝑤𝑖 which is as high as interesting city seems to Alex.

Alex believes that his trip will be interesting only if he will not use any road twice in a row. That is if Alex came to city 𝑣 from city 𝑢, he may choose as the next city in the trip any city connected with 𝑣 by the road, except for the city 𝑢.

Your task is to help Alex plan his city in a way that maximizes total score over all cities he visited. Note that for each city its score is counted at most once, even if Alex been there several times during his trip.

链接🔗

「CodeForces 1220E」 Tourism

题解

边双缩点后跑树形DP吧。
代码巨丑无比，写了好久，看来点双板子得改改了。

代码

const int maxd = 2e5+10;
typedef long long ll;
ll dfn[maxd],low[maxd],tot,stk[maxd],top,n,m,sz[maxd];
ll belong[maxd],scc,sum[maxd];
bool use[maxd<<1],inq[maxd];
 
P e[maxd<<4];
ll eid,f[maxd<<2],v[maxd];
void init()
{
    memset(f,-1,sizeof(f));
    eid = 0;
}
void insert(ll x,ll y)
{
    e[eid].ST = y, e[eid].ND = f[x] , f[x] = eid++;
}
void tarjan(ll x)
{
    low[x] = dfn[x] = ++tot;
    stk[top++] = x, inq[x] = 1;
//    PLL(x); putchar('-');
//    PN();
    for(int i = f[x];i+1; i=e[i].ND)
    {
        if(use[i]) continue;
        ll v = e[i].ST;
        //PLL(v); PN();
 
        if(!dfn[v])
        {
            use[i] = use[(i&1)?i-1:i+1] = 1;
            tarjan(v);
            use[i] = use[(i&1)?i-1:i+1] = 0;
            low[x] = min(low[x],low[v]);
        }
        else if(inq[v]) low[x] = min(low[x],dfn[v]);
    }
    if(low[x] == dfn[x])
    {
        scc++;
        do
        {
            belong[stk[--top]] = scc;
            sum[scc] += v[stk[top]];
            sz[scc]++;
            inq[stk[top]] = false;
        }while(stk[top]!=x);
    }
}
ll dp[maxd],ans,vis[maxd];
int dfs(ll x)
{
    dp[x-n] += sum[x-n];
    vis[x-n] = 1;
    int flag = 0;
    for(ll i = f[x];i+1;i=e[i].ND)
    {
        ll v = e[i].ST;
        if(vis[v-n]) continue;
 
        if(dfs(v))
        {
            flag = 1;
            dp[x - n] += dp[v - n];
            dp[v - n] = 0;
        }
    }
    return sz[x-n]>2 || flag;
}
void dfs1(ll x)
{
    ans = max(ans,dp[x-n]);
 
    //PLL(x-n);PN();
    vis[x-n] =1;
    for(ll i = f[x];i+1;i=e[i].ND)
    {
        ll v = e[i].ST;
        //PLL(v-n);PP();PLL(vis[v-n]);PN();
        if(vis[v-n]) continue;
        dp[v-n] += dp[x-n];
        dfs1(v);
    }
}
int main()
{
    //__IN;__OUT;
    RLL(n);RLL(m);
    init();
    FOR(i,1,n) RLL(v[i]);
    FOR(i,1,m)
    {
        ll x,y;RLL(x);RLL(y);
        insert(x,y); insert(y,x);
    }
    FOR(i,1,n) if(!dfn[i]) tarjan(i);
//    FOR(i,1,n)
//    {
//        PLL(belong[i]);
//        PN();
//    }
    FOR(i,1,n)
        for(int j = f[i];j+1;j=e[j].ND)
        {
            ll x = belong[e[j].ST],y = belong[i];
            if(x!=y)
            {
                //PLL(x);PP();PLL(y);PN();
                insert(x+n,y+n);
                insert(y+n,x+n);
            }
        }
 
        //PLL(f1[belong[2]]); PN();
    ll k; RLL(k);
    dfs(belong[k]+n);
    FOR(i,1,scc)
    {
        vis[i] = 0;
//        PLL(dp[i]);
//        PN();
    }
 
    dfs1(belong[k]+n);
    PLL(ans);
    return 0;
}