我把环的两条相邻的边拆开了之后做dfs,考虑到找到环后是直接退出,需要在Dp的时候把vis标记打上,但是为啥这样做是错的?
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T>
inline void read(T& x){
x = 0; bool f = 0; char c = getchar();
while(c < '0' || c > '9'){f = c == '-'; c = getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
if(f) x = -x;
}
const int maxN = 1E6 + 5;
int head[maxN], cnt = 0, w[maxN], n, r, e1, e2;
bool vis[maxN], hasCircle;
struct edge{
int to, next;
edge(int to = 0, int next = -1):to(to), next(next){}
}edges[maxN << 1];
inline void add(int u, int v){
edges[cnt] = edge(v, head[u]);
head[u] = cnt++;
}
struct node{
ll single, tot;
node(ll single, ll tot):single(single), tot(tot){}
};
inline void findCircle(int now, int pre){
vis[now] = 1;
for(int e = head[now]; ~e; e = edges[e].next){
int& to = edges[e].to;
if(e == (pre ^ 1)) continue;
if(vis[to]){
r = now;
e1 = e ^ 1;
hasCircle = 1;
return ;
}
findCircle(to, e);
if(hasCircle){
if(e2 == -1) e2 = e;
return ;
}
}
}
inline node dfs(int now, int pre, int r){
vis[now] = 1;
ll fir = 0, sec = 0, tot = 0;
for(int e = head[now]; ~e; e = edges[e].next){
int& to = edges[e].to;
if(e == (pre ^ 1) || to == r) continue;
auto it = dfs(to, e, r);
tot = max(tot, it.tot);
ll nS = it.single + w[e >> 1];
if(nS >= fir) swap(fir, sec), fir = nS;
else if(nS > sec) sec = nS;
}
return node(fir, max(fir + sec, tot));
}
inline void getAns(){
ll res = 0;
for(int i = 1; i <= n; i++){
hasCircle = 0;
e1 = e2 = -1;
if(!vis[i]){
findCircle(i, -1);
if(hasCircle) res += max(dfs(r, e1, r).tot, dfs(r, e2, r).tot);
else res += dfs(i, -1, -1).tot;
}
}
printf("%lld", res);
}
int main(){
int to;
read(n);
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++){
read(to), read(w[i - 1]);
add(to, i);
add(i, to);
}
getAns();
return 0;
}