1a:I[10086,["6079","static/chunks/363642f4-ca12a5ed7d30075e.js","5653","static/chunks/5653-10777e0e1fc92dce.js","5000","static/chunks/5000-a7bfe5b9669501e3.js","5538","static/chunks/5538-ed47f067afaa5003.js","7412","static/chunks/7412-2a540dc7a2630d42.js","643","static/chunks/app/codes/%5Bid%5D/page-8bf5a5fa194d2ba8.js"],"AdSenseInsert"] 1b:I[48803,["6079","static/chunks/363642f4-ca12a5ed7d30075e.js","5653","static/chunks/5653-10777e0e1fc92dce.js","5000","static/chunks/5000-a7bfe5b9669501e3.js","5538","static/chunks/5538-ed47f067afaa5003.js","7412","static/chunks/7412-2a540dc7a2630d42.js","643","static/chunks/app/codes/%5Bid%5D/page-8bf5a5fa194d2ba8.js"],"CodeViewer"] 1c:T67b,#include using namespace std; using ll = long long; struct NodeInfo { ll sum; int flip; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector F(N+1), B(N+1); for (int i=1;i<=N;++i) cin >> F[i]; for (int i=1;i<=N;++i) cin >> B[i]; vector> g(N+1); for (int i=0,u,v;i> u >> v; g[u].push_back(v); g[v].push_back(u); } vector parent(N+1); vector order; order.reserve(N); // iterative DFS to get post-order stack st; st.push(1); parent[1]=0; while(!st.empty()){ int u=st.top(); st.pop(); order.push_back(u); for(int v:g[u]) if(v!=parent[u]){ parent[v]=u; st.push(v);} } reverse(order.begin(), order.end()); // children 먼저 vector> DP(N+1); // [p=0], [p=1] for(int u: order){ for(int p=0;p<2;++p){ // 두 후보 t=0,1 NodeInfo best{ll(-1e9), INT_MAX}; for(int t=0;t<=1;++t){ int pu = p ^ t; // parity at u ll candSum = (pu? B[u]: F[u]); int candFlip = t; for(int v: g[u]) if(v!=parent[u]){ candSum += DP[v][pu].sum; candFlip += DP[v][pu].flip;

코드 #2812