从题目给的条件其实可以发现数据可以是一个基环树森林。(猜测可能数据不是 没有作死去人肉试过)
基环树是一种图,它由一个环组成,环上每个点都是一棵树点树根,所以称为基环树。当然,一棵树上连一条边也会变成基环树。
如果本题取消条件是基环树而是一棵树,那么问题便简化为了
没有上司的舞会,处理方法就是简单的树形DP。
而基环树问题重要的肯定就是断环,那么我们可以延伸思考一个问题,一个点在树上只有选和不选两种状态,所以可以出现一道处理方式相关的有向基环树题目 创世纪
因为本题不需要枚举每个节点只需要环上每个节点所以可以使用并查集找环 打了可持久化好写又快速 并查集可以说是非常重要的数据结构了 不会的快学!(都做骑士了都应该会吧)
而这道题当保证自己不选的时候儿子是随意的,所以代码会简洁一点
而本题因为是无向图,所以只需要对断边的两个节点进行,一次DP,并且记录不其节点的答案,max比较就可以了
本题最后一个题卡常严重 用力卡也可以过 或者…… 你可以开o2 或者打表
现在贴上code【由于卡常 部分代码可能过于余赘】
#include #include #include #include #include #include #define LL long long using namespace std; const LL maxn=1000010; inline void read(int &x){ x=0;int f=1;char c=getchar(); while(c>'9'||c } while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); x*=f; } struct node{ int v,nxt; }e[maxn<<1]; int head[maxn],tot; inline void add(int x,int y) { tot++; e[tot].v = y; e[tot].nxt = head[x]; head[x] = tot; } int w[maxn],fa[maxn]; inline LL find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } int n,a[maxn],b[maxn],tmp,cnt,nowa; LL f[maxn],g[maxn],tmpp;//f选 g不选 inline void dfs(LL u,LL fa) { f[u]=w[u]; g[u]=0; for(int i=head[u];i;i=e[i].nxt) { LL v=e[i].v; if(v==fa||v==nowa) continue; dfs(v,u); if(g[v]>f[v]) g[u]+=g[v]; else g[u]+=f[v];//就是max f[u]+=g[v]; } } LL ans; int main() { read(n); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) { read(w[i]),read(tmp); if(find(tmp)!=find(i)) { add(tmp,i); add(i,tmp); fa[fa[tmp]]=fa[i]; } else { cnt++; a[cnt]=tmp; b[cnt]=i; } } for(int i=1;i<=cnt;i++) { nowa = a[i]; dfs(a[i],0); tmpp = g[a[i]]; nowa = b[i]; dfs(b[i],0); if(tmpp>g[b[i]]) ans+=tmpp; else ans+=g[b[i]]; } printf("%lld",ans); return 0; }