.net怎么做网站,wordpress 电影网站模板,php网站开发教程网,wordpress动态标题P2495 [SDOI2011]消耗战
题目描述
详见#xff1a;P2495 [SDOI2011]消耗战
Solution
此题是虚树的经典版子题吧qwq。
是不是直接贴代码就行了啊#xff08;反正不是luogu题解#xff0c;没有人查#xff09;。
大概就是先建出虚树#xff08;一般给定一堆关键点的题…P2495 [SDOI2011]消耗战
题目描述
详见P2495 [SDOI2011]消耗战
Solution
此题是虚树的经典版子题吧qwq。
是不是直接贴代码就行了啊反正不是luogu题解没有人查。
大概就是先建出虚树一般给定一堆关键点的题都是虚树然后DP。
设为处理掉子树中所有关键点的最小花费 为从到根的路径上的最小边权。 然后……没了。
Code
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int MAXN5e550;
const ll INF1ll60;
int Log[MAXN],fa[MAXN][21],dfn[MAXN],dep[MAXN];
int stk[MAXN],a[MAXN],top,DFN0;
ll mn[MAXN],f[MAXN];
struct enode{int to; ll c; };
vectorenode e[MAXN];
vectorint son[MAXN];inline int read()
{int x0,f1; char cgetchar();while (c0||c9) { if(c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
void add_edge(int u,int v){ son[u].push_back(v); }
void dfs(int x,int father)
{fa[x][0]father;dep[x]dep[father]1;dfn[x]DFN;for (int i1;iLog[dep[x]];i) fa[x][i]fa[fa[x][i-1]][i-1];for (int i0;ie[x].size();i)if (e[x][i].to!father){mn[e[x][i].to]min(mn[x],e[x][i].c);dfs(e[x][i].to,x);}
}
int get_lca(int x,int y)
{if (dep[x]dep[y]) swap(x,y);for (int iLog[dep[x]];i0;i--)if (dep[fa[x][i]]dep[y]) xfa[x][i];if (xy) return x;for (int iLog[dep[x]];i0;i--)if (fa[x][i]!fa[y][i]) xfa[x][i],yfa[y][i];return fa[x][0];
}
void insert(int x)
{if (top1) { stk[top]x; return; }int lcaget_lca(stk[top],x);if (lcastk[top]) return;while (top1dfn[stk[top-1]]dfn[lca]) add_edge(stk[top-1],stk[top]),top--;if (lca!stk[top]) add_edge(lca,stk[top]),stk[top]lca;stk[top]x;
}
ll tree_dp(int x)
{for (int i0;ison[x].size();i) tree_dp(son[x][i]);f[x]mn[x];if (!son[x].size()) return f[x];ll s0;for (int i0;ison[x].size();i) sf[son[x][i]];son[x].clear();return f[x]min(f[x],s);
}
int compare(int x,int y){ return dfn[x]dfn[y]; }
int main()
{int nread();for (int i1;in;i){int uread(),vread(),cread();e[u].push_back((enode){v,c});e[v].push_back((enode){u,c});}dep[0]-1,Log[1]0;for (int i2;in;i) Log[i]Log[i1]1;for (int i1;in;i) mn[i]INF; dfs(1,0);//for (int i1;in;i) couti:dep[i] dfn[i] mn[i]endl;int Caseread();while (Case--){int mread();for (int i1;im;i) a[i]read();sort(a1,am1,compare);stk[top1]1;for (int i1;im;i) insert(a[i]);while (top) add_edge(stk[top-1],stk[top]),top--;printf(%lld\n,tree_dp(1));}return 0;
}
