万能识图,泉州seo 泉州网站建设,wordpress程序主题,网站做优化一开始怎么做正题
题目链接:https://www.luogu.com.cn/problem/P2495 题目大意 nnn个点的一棵树#xff0c;mmm次给出一些点#xff0c;要求割掉最小权值的边使得这些点不和111号点联通。 解题思路
根据这些给出的点构造一棵虚树#xff0c;然后直接dpdpdp求解即可。 codecodecode
#i…正题
题目链接:https://www.luogu.com.cn/problem/P2495 题目大意
nnn个点的一棵树mmm次给出一些点要求割掉最小权值的边使得这些点不和111号点联通。 解题思路
根据这些给出的点构造一棵虚树然后直接dpdpdp求解即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N3e510,T20,inf1e18;
struct node{ll to,next,w;
}a[N*2];
ll n,m,tot,cnt,st,k,dep[N],dfn[N],ls[N],p[N];
ll f[N][T1],g[N][T1],pos[N],s[N],dp[N][2];
bool cmp(ll x,ll y)
{return dfn[x]dfn[y];}
void addl(ll x,ll y,ll w){if(dep[x]dep[y])swap(x,y);a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(ll x,ll fa){dfn[x]cnt;dep[x]dep[fa]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;f[y][0]x;g[y][0]a[i].w;dfs(y,x);}return;
}
ll LCA(ll x,ll y){if(dep[x]dep[y])swap(x,y);for(ll iT;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy)return x;for(ll iT;i0;i--)if(f[y][i]!f[x][i])xf[x][i],yf[y][i];return f[x][0];
}
ll Dis(ll x,ll y){ll ansinf;if(dep[x]dep[y])swap(x,y);for(ll iT;i0;i--)if(dep[f[y][i]]dep[x])ansmin(ans,g[y][i]),yf[y][i];return ans;
}
void ins(ll x){if(!st){s[st]x;return;}ll lcaLCA(x,s[st]);while(st1dep[s[st-1]]dep[lca])addl(s[st-1],s[st],Dis(s[st-1],s[st])),st--;if(dep[s[st]]dep[lca])addl(lca,s[st],Dis(lca,s[st])),st--;if((!st)||(lca!s[st]))s[st]lca;s[st]x;return;
}
void solve(ll x){if(pos[x])dp[x][1]0,dp[x][0]inf;else dp[x][0]0,dp[x][1]0;for(ll ils[x];i;ia[i].next){ll ya[i].to;solve(y);dp[x][0]min(dp[y][0],dp[y][1]a[i].w);dp[x][1]min(dp[x][0]dp[y][1],min(dp[x][1]dp[y][0],dp[x][1]dp[y][1]));}ls[x]pos[x]0;return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}memset(g,0x3f,sizeof(g));dfs(1,0);for(ll j1;jT;j)for(ll i1;in;i)f[i][j]f[f[i][j-1]][j-1],g[i][j]min(g[i][j-1],g[f[i][j-1]][j-1]);memset(ls,0,sizeof(ls));scanf(%lld,m);while(m--){scanf(%lld,k);sttot0;for(ll i1;ik;i){scanf(%lld,p[i]);pos[p[i]]1;}sort(p1,p1k,cmp);s[st]1;for(ll i1;ik;i)ins(p[i]);while(st1)addl(s[st-1],s[st],Dis(s[st-1],s[st])),st--;solve(1);printf(%lld\n,dp[1][0]);}return 0;
}
