【ZJOI2008】骑士

题面

https://www.luogu.org/problem/P2607

题解

这道题让我回想起了省选前被$aysn$吊打的故事。

本应该用$tarjan$找环，但是我当年太弱了，写的并查集找环。

最大独立集$dp$（当年我连最大独立集$dp$都不会。说不定现在也不会呢）。

#include<cstdio>
#include<iostream>
#include<vector>
#define ll long long
#define ri register int
#define N 1000050
#define INF 987654321*987654321LL
#include<set>
using namespace std;
int a[N];
int n;
int p[N],q[N];
vector<int> to[N];
set<pair<int,int> > s;
ll f[N][2];

ll max(ll a,ll b){
  if (a>b) return a; else return b;
}

struct binchaji{
  int f[N];
  void clear(){
    for (ri i=1;i<=n;i++) f[i]=i;
  }
  int findroot(int x){
    if (f[x]==x) return x;
    return f[x]=findroot(f[x]);
  }
  void merge(int x,int y){
    f[findroot(x)]=findroot(y);
  }
} ylq;

void dp(int x,int fob,int ff){
  f[x][0]=0; f[x][1]=a[x];
  if (x==fob) f[x][1]=-INF;
  for (ri i=to[x].size()-1;i>=0;i--) if (to[x][i]!=ff) {
    dp(to[x][i],fob,x);
    f[x][0]+=max(f[to[x][i]][0],f[to[x][i]][1]);
    f[x][1]+=f[to[x][i]][0];
  }
}

int getint(){
  char ch=getchar();
  int x=0;
  while (ch<'0' || ch>'9') ch=getchar();
  while (ch>='0' && ch<='9') x=x*10+(ch-'0'),ch=getchar();
  return x;
}

int main(){
  n=getint();
  ylq.clear();
  int cnt=0,v;
  for (ri i=1;i<=n;i++) {
    a[i]=getint(); v=getint();
    int x=i,y=v;
    if (x>y) swap(x,y);
    if (ylq.findroot(i)!=ylq.findroot(v)) {
      to[i].push_back(v);
      to[v].push_back(i);
      ylq.merge(i,v);
    }
    else if (!s.count(make_pair(x,y))) {
      s.insert(make_pair(x,y));
      p[++cnt]=x; q[cnt]=y;
    }
  }
  
  ll ans=0;
  ll s1,s2;
  for (ri i=1;i<=cnt;i++) {
    dp(p[i],p[i],-1);
    s1=max(f[p[i]][0],f[p[i]][1]);
    dp(p[i],q[i],-1);
    s2=max(f[p[i]][0],f[p[i]][1]);
    ans+=max(s1,s2);
  }
  cout<<ans<<endl;
}