【Codeforces Round#586(Div.1+Div.2)E.Tourism】Tarjan縮点+ツリーDP

タイトルリンク
http://codeforces.com/contest/1220/problem/E
に言及
n個の点m辺の無方向連通図をあげて、各点に点権があって、今起点sを与えて、1本の点権と最大の経路を探し出して、同じ辺を2回連続的に歩くことができなくて、しかも何度も同じ点を通った時、1回の点権しか得られません.
1 ≤ n , m ≤ 2 ∗ 1 0 5 1\leq n,m\leq 2*10^5 1≤n,m≤2∗105
やり方
問題を分析すると、図面にリングが現れなければ、リングの各点を一度遍歴し、任意の点からリングを出ることができることが分かった.そこで1つの環の中の点は運命共同体になったので、私たちはまず縮点を選んで、縮点した後に1本の木になって、私たちはSを根にして、木の上でDPを行うことができます.DP方程式の定義は
sum[rt]は縮点後の各連通成分の重みを表し、dp[rt][0]はrtをルートとするサブツリー内でrtからrtに戻る最大重み経路を表し、dp[rt][1]はrtをルートとするサブツリー内でrtから出発する最大重み経路を表し、まず葉ノードごとに葉ノードが存在する連通成分点数が2を超えると、d p[r t][0]=d p[r t][1]=s u m[r t]dp[rt][0]=dp[rt][1]=sum[rt]dp[rt][0]=dp[rt][1]=sum[rt]でなければd p[r t][1]=s u m[r t]dp[rt][1]=sum[rt]dp[rt][1]=sum[rt]dp[rt][1]=sum[rt]dp[rt][1]=sum[rt]各非葉ノードについて、まずすべての息子の中でルートノードに戻ることができるdp値を加算することで、必ずルートノードに戻ることができることを保証します.その後、サブツリー全体にルートノードに戻るリングがあるかどうかを見てみましょう.ある場合、d p[r t][0]dp[rt][0]dp[rt][0]はすべてのd p[t o][0]dp[to][0]dp[to][0]dp[to][0]に等しいことがあります.の和にs u m[r t]sum[rt]sum[rt]を加え、そうでなければd p[r t][0]=0 dp[rt][0]=0 dp[rt][0]=0である.その後、d p[r t][1]dp[rt][1]dp[rt][1]dp[rt][1]がどのように移行するかを見て、まず、すべてのd p[t o][r t]dp[to][rt]dp[to][rt]の和を得て、すべてのt o to toの中から、1つのd p[t o][1]−d p[t o][0]dp[to][1]−dp[to][0]dp[to][1]−dp[to][0]が最大であり、それを返す必要のない経路とすればよいし、サブツリー内にリングが存在するかどうかにかかわらず、d p[r t][1]dp[rt][1]dp[rt][1]dp[rt][1]にs u m[r t]sum[rt]sum[rt]を加えなければならない.
コード#コード#

#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 4e5+10;
#define Fi first
#define Se second
#define dbg(x) cout<
#define pb push_back
#define dbg(x) cout<
#define dbg2(x1,x2) cout<
#define dbg3(x1,x2,x3) cout<
int low[maxn],dfn[maxn],root[maxn],cnt,sum,tot,head[maxn],fa[maxn],num[maxn],flag[maxn],val[maxn];
map<pii,int> mp;
vector<int> G[maxn];
ll arr[maxn],dp[maxn][2],can[maxn];
struct node
{
    int to,nxt;
};
node edge[maxn*4];
int Find(int x)
{
    return x==root[x]?x:root[x]=Find(root[x]);
}
void  uno(int x,int y)
{
    int fx=Find(x),fy=Find(y);
    if(fx!=fy) root[fy]=fx;
}
void addedge(int u,int v)
{
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
void tarjan(int u,int fat)
{
    dfn[u]=low[u]=++cnt;
    fa[u]=fat;
    int ff=0;
    for(int i=head[u];i+1;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]<=dfn[u]) uno(u,v);
        }
        else if(dfn[v])
        {
            if(v==fat)
            {
                if(ff==0) ff++;
                else ff=0,low[u]=min(low[u],dfn[v]);
            }
            else if(v!=fat) low[u]=min(low[u],dfn[v]);
        }
    }
}
void dfs(int rt,int fa)
{
    if(num[rt]>=2) can[rt]=1;
    ll maxx=0;
    for(int i=0;i<G[rt].size();i++)
    {
        int to=G[rt][i];
        if(to==fa) continue;
        dfs(to,rt);
        dp[rt][0]+=dp[to][0];
        maxx=max(maxx,dp[to][1]-dp[to][0]);
        can[rt]|=can[to];
    }
    dp[rt][1]=dp[rt][0]+maxx+arr[rt];
    if(can[rt]) dp[rt][0]+=arr[rt];
    else dp[rt][0]=0;
}
int main()
{
    //freopen("E.in","r",stdin);
    int n,m,s;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)  { head[i]=-1; root[i]=i; }
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    scanf("%d",&s);
    tarjan(1,1);
    for(int i=1;i<=n;i++) fa[i]=Find(i);
    int cnt=0;
    for(int i=1;i<=n;i++) if(fa[i]==i) flag[i]=++cnt;
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j+1;j=edge[j].nxt)
        {
            int u=i;
            int v=edge[j].to;
            if(fa[u]==fa[v]) continue;
            int x=flag[fa[u]];
            int y=flag[fa[v]];
            if(mp.find(pii(x,y))!=mp.end()) continue;
            mp[pii(x,y)]=1;
            G[x].push_back(y);
        }
    }
    for(int i=1;i<=n;i++) num[flag[fa[i]]]++,arr[flag[fa[i]]]+=val[i];
    dfs(flag[fa[s]],-1);
    printf("%lld
",dp[flag[fa[s]]][1]);
    return 0;
}