码蹄杯刷题

目录树形dpM0560数据结构MC0562树形dpM0560思路括号的性质前缀后缀和不能为负数令dp[u][val]为转移到u时后缀为val的方案数dp[u][val]可能由两种状态转移过来dp[v][val1]dp[v][val-1]两种状态内部的每一个子节点v是相对独立的所以可以进行累乘而dp[u][val]的方案数是两种方案数的总和代码void solve(){ int n;cinn; vectorvectorint g(n10); for(int i1;in-1;i){ int u,v;cinuv; g[u].push_back(v),g[v].push_back(u); } if(n1){ cout0endl; return; } vectorvectorint dp(n10,vectorint(n10)); auto dfs[](auto dfs,int u,int fa)-void{ for(auto v:g[u]){ if(vfa) continue; dfs(dfs,v,u); } if(g[u].size()1u!1){ dp[u][1]1; return; } for(int val0;valn;val){ int res11; if(valn-1){ for(auto v:g[u]){ if(vfa) continue; res1res1*dp[v][val1]%mod; } } else res10; int res21; if(val){ for(auto v:g[u]){ if(vfa) continue; res2res2*dp[v][val-1]%mod; } } else res20; dp[u][val](res1res2)%mod; } };dfs(dfs,1,-1); coutdp[1][0]endl; }数据结构MC0562思路并查集贪心代码:int p[N],cnt[N],edg[N]; int find(int x){ if(xp[x]) return x; return p[x]find(p[x]); } void merge(int a,int b){ int xfind(a),yfind(b); // if(xy) swap(x,y); edg[x]1; if(xy) return; cnt[x]cnt[y]; edg[x]edg[y]; p[y]x; } void solve(){ int n,m;cinnm; for(int i1;in;i) p[i]i,cnt[i]1; for(int i1;im;i){ int u,v;cinuv; merge(u,v); } int ans0; for(int i1;in;i){ if(ifind(i)){ //couti cnt[i] edg[i]endl; if(cnt[i]%2edg[i]%2) anscnt[i]; else anscnt[i]-1; } } coutans; }