Problem:


Escape

頂点に正の値を持つ無向グラフが与えられる。
頂点には 1 から N の番号がついており、i 番目の頂点は w_i の値を持っている。
1 番目の頂点からスタートし、直前に通った辺を通ることができないという制約のもとでグラフ上を移動することができる。
各頂点では，初めて訪れた時に限りその頂点が持つ値の点数を得られる。

取得できる点数の総和の最大値を求めよ。

Constraints

1  ≤  N  ≤  100000

N &minus; 1  ≤  M  ≤  100000

1  ≤  w_i  ≤  1000

1  ≤  u_i, v_i  ≤  N

多重辺・自己辺は存在しない

グラフは連結である

Input Format

入力は以下の形式で標準入力から与えられる。

N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
...
u_M v_M

1 行目にはグラフの頂点数 N と辺の数を表す整数 M が入力される。 

2 行目には各頂点が持つ値 w_i が入力される。 

さらに続けて M 行に、各辺により繋がれる 2 頂点の番号が入力される。

Output Format

答えを1行に出力せよ。

Sample Input 1

6 6
1 2 3 4 5 6
1 2
2 3
3 4
1 4
4 5
5 6

Sample Output 1

21

 

頂点 1→2→3→4→5→6 と進むことで全ての頂点の点数を集めることができます。

Sample Input 2

7 8
1 3 3 5 2 2 3
1 2
2 3
3 1
1 4
1 7
1 5
1 6
5 6

Sample Output 2

16

 

頂点 1→2→3→1→5→6→1→4 と進むことで16点を集めることができます。



Sample input:
6 6
1 2 3 4 5 6
1 2
2 3
3 4
1 4
4 5
5 6


Sample output:
21

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    N, M = map(int, readline().split())
    *W, = map(int, readline().split())
    G = [[] for i in range(N)]
    for i in range(M):
        u, v = map(int, readline().split())
        G[u-1].append(v-1)
        G[v-1].append(u-1)
    U = [0]*N
    L = [0]*N
    D = [0]*N
    R = [0]*N

    U[0] = 1
    stk = [0]
    it = [0]*N
    while stk:
        v = stk[-1]
        p = stk[-2] if len(stk) > 1 else -1
        if it[v] == 0:
            U[v] = 1
        else:
            w = G[v][it[v]-1]
            D[v] = max(D[v], D[w])
            if L[w]:
                L[v] = 1

        while it[v] < len(G[v]):
            w = G[v][it[v]]; it[v] += 1
            if U[w]:
                if w != p:
                    L[v] = 1
                continue
            U[w] = 1
            stk.append(w)
            break
        else:
            D[v] = D[v] + W[v]
            stk.pop()

    ans = su = 0
    for i in range(N):
        if L[i]:
            ans += W[i]
        else:
            su = max(su, D[i])
    write("%d\n" % (ans + su))
solve()

Submission status: Accepted

Solution code:
# 前の提出は1が葉のときまずかったので再提出。

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
W=[0]+list(map(int,input().split()))
E=[tuple(map(int,input().split())) for i in range(m)]
S=1

ELIST=[[] for i in range(n+1)]
EW=[0]*(n+1)

for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)

    EW[x]+=1
    EW[y]+=1


from collections import deque
Q=deque()
USED=[0]*(n+1)

for i in range(1,n+1):
    if EW[i]==1 and i!=S:
        USED[i]=1
        Q.append(i)

EW[S]+=1<<50
USED[S]=1

while Q:
    x=Q.pop()
    EW[x]-=1

    for to in ELIST[x]:
        if USED[to]==1:
            continue
        EW[to]-=1

        if EW[to]==1 and USED[to]==0:
            Q.append(to)
            USED[to]=1

#print(EW)
LOOP=[]

ANS=0
for i in range(1,n+1):
    if EW[i]!=0:
        ANS+=W[i]
        LOOP.append(i)

SCORE=[0]*(n+1)
USED=[0]*(n+1)

for l in LOOP:
    SCORE[l]=ANS
    USED[l]=1

Q=deque(LOOP)

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if USED[to]==1:
            continue

        SCORE[to]=W[to]+SCORE[x]
        Q.append(to)
        USED[to]=1

print(max(SCORE))

Submission status: Accepted

Solution code:
def find(x):
  if par[x] == x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def union(x, y):
  par_x = find(x)
  par_y = find(y)
  if rank[par_x] < rank[par_y]:
    par[par_x] = par_y
    w[par_y]+=w[par_x]
  else:
    par[par_y] = par_x
    w[par_x]+=w[par_y]
    if rank[par_x] == rank[par_y]:
      rank[par_x] += 1

def same(x, y):
  return find(x)==find(y)

def dfs(cur, prev):
  if visited[cur] or cur!=find(cur):
    while len(path)>0:
      union(0, path.pop())
    return
  visited[cur] = 1
  path.append(cur)
  for to in graph[cur]:
    if to==prev:
      continue
    dfs(to, cur)
  visited[cur] = 0
  if len(path)>0 and path[-1]==cur:
    path.pop()

def dfs2(cur):
  visited[cur] = 1
  ret = 0
  for i in range(len(graph2[cur])):
    for ele in graph[graph2[cur][i]]:
      if visited[find(ele)] == 0:
        ret = max(ret, dfs2(find(ele)))
  return ret+w[find(cur)]

import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
w = [0]
w.extend(list(map(int, input().split())))
graph = defaultdict(list)
for _ in range(m):
  u, v = map(int, input().split())
  graph[u].append(v)
  graph[v].append(u)

path = []
graph2 = [[] for _ in range(n+1)]
visited = [0]*(n+1)
par = [i for i in range(n+1)]
rank = [0]*(n+1)

dfs(1, -1)
for i in range(1, n+1):
  graph2[find(i)].append(i)

print(dfs2(find(1)))