题目大意：给定一个基环树林，每一个点上有权值，要求选择一个权值和最大的点集，要求点集中的随意两个点之间不能直接相连
最大点独立集……考虑到n<=100W，网络流铁定跑不了，于是我们考虑树形DP
对于每棵基环树，我们找到环上的一条边，设边上的两端点分别为u和v，f[i]为以i为根的子树在取i点的情况下的最大权值。g[i]为不取，于是我们有下面做法：
1.断掉这条边
2.u不取。v随意。我们以u为根跑一遍树形DP，取g[u]
3.v不取，u随意，我们以v为根跑一遍树形DP，取g[v]
4.取上述两个值中的最大值，记入ans
非常不错的一道题 能够拿来练练基环树 也许能够写写Island？
70%达成 冻死我了 碎叫去
#include#include #include #include #define M 1001001using namespace std;typedef long long ll;struct abcd{ int to,next;}table[M<<1];int head[M],tot=1;int n,a[M],v[M],U,V,E;ll f[M],g[M],ans;//f-选 g-不选 void add(int x,int y){ table[++tot].to=y; table[tot].next=head[x]; head[x]=tot;}void dfs(int x,int from){ int i; v[x]=1; for(i=head[x];i;i=table[i].next) { if( (i^1)==from ) continue; if(v[table[i].to]) { U=x; V=table[i].to; E=i; continue; } dfs(table[i].to,i); }}void Tree_DP(int x,int from,int ban){ int i; f[x]=a[x]; g[x]=0; for(i=head[x];i;i=table[i].next) { if( i==ban || (i^1)==ban ) continue; if( (i^1)==from ) continue; Tree_DP(table[i].to,i,ban); f[x]+=g[table[i].to]; g[x]+=max(f[table[i].to],g[table[i].to]); }}int main(){ int i,x; cin>>n; for(i=1;i<=n;i++) { scanf("%d%d",&a[i],&x); add(i,x); add(x,i); } for(i=1;i<=n;i++) if(!v[i]) { dfs(i,0); Tree_DP(U,0,E); ll temp=g[U]; Tree_DP(V,0,E); temp=max(temp,g[V]); ans+=temp; } cout< <