蓟州农家院如何做网站,网站建设有哪些推广渠道,深圳网站建设哪里便宜,达州大亚网站建设https://www.luogu.com.cn/problem/P2495
虚树#xff1a;当我们在解决树形dp的问题的时候#xff0c;题目中会给出一些询问#xff0c;询问涉及的关键节点不多#xff0c;并保证总的点数规模的时候#xff0c;我们就可以使用虚数#xff0c;如果每次询问都对整个树进行…https://www.luogu.com.cn/problem/P2495
虚树当我们在解决树形dp的问题的时候题目中会给出一些询问询问涉及的关键节点不多并保证总的点数规模的时候我们就可以使用虚数如果每次询问都对整个树进行dp的话显然会超市。要注意每一次的初始化
题目给出n点有n-1条带权边有q个询问每次给出k个点询问要使得这k个点和1号节点不连通需要移除的边的总权值最小是多少。
思路
令dp[n]表示从nn开始不能到达其子树中的关键点所需切断的最小边权和.
令me[u]表示切断11到uu的路径中的边权最小值.
设vv是uu的直接儿子.
如果vv是关键节点,那么dp[u]me[v],否则dp[u]min(me[v],dp[v]) (第2个转移方程的解释:要么直接切断1−v的路径,要么使得从v出发不能到达其子树的关键点.)
显然我们不能针对每个询问对整颗子树进行dpdp,时间复杂度过高,而我们发现那些非关键点我们没有必要在dp的时候考虑,所以使用虚树.
参考大神题解
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include cstdlib
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se second
#define scd(a) scanf(%d,a)
#define scdd(a,b) scanf(%d%d,a,b)
#define scddd(a,b,c) scanf(%d%d%d,a,b,c)
#define ac coutans\n
#define F(x) ((x)/3((x)%31?0:tb))
#define G(x) ((x)tb?(x)*31:((x)-tb)*32)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod1e97;
const ll N 250007;
const ll M 250000;
const double eps 1e-4;
//const double piacos(-1);
ll qk(ll a,ll b){ll ans1;while(b){if(b1) ans(ans*a)%mod;a(a*a)%mod;b/2;}return ans%mod;}
int n;
int cnt,m;
int ldfn[N],rdfn[N];//当前节点的dfs序
int fa[N][20];//f[i][j]表示i节点向上2^j步的祖先
int dep[N];//节点深度
int stk[N];//栈用于构建虚树
int d[N1];//用于存储虚树的节点编号。由于LCA可能有重复因此需要开2倍
int vis[N];//标记当前节点是否为关键点
vectorpii RG[N];
vectorint VG[N];
ll me[N];
void predfs(int u,int f,int depth)
{ldfn[u]cnt;dep[u]depth;fa[u][0]f;for(int j1;j20;j){fa[u][j]fa[fa[u][j-1]][j-1];}for(pii k:RG[u]){int vk.fi;if(vf) continue;me[v]k.second;if(u!1) me[v]min(me[u],me[v]);predfs(v,u,depth1);}rdfn[u]cnt;
}int lca(int u,int v)
{if(dep[u]dep[v])swap(u,v);int deltadep[u]-dep[v];for(int j0;j20delta;j){if(delta(1j))ufa[u][j];}if(uv) return u;for(int j20-1;j0;j--){if(fa[u][j]!fa[v][j]){ufa[u][j];vfa[v][j];}}return fa[u][0];
}bool cmp(int x,int y)
{return ldfn[x]ldfn[y];
}void build()
{sort(d1,dm1,cmp);int keynumm;for(int i1;ikeynum;i) d[m]lca(d[i],d[i1]);sort(d1,dm1,cmp);munique(d1,dm1)-d-1;int top0;stk[top]d[1];for(int i2;im;i){while(toprdfn[stk[top]]ldfn[d[i]])top--;if(top)VG[stk[top]].push_back(d[i]);stk[top]d[i];}
}
ll DP(int u){ll cost0;for(int v:VG[u]){costmin(me[v],DP(v));}VG[u].clear();//初始化if(vis[u]) return me[u];else return cost;
}
void sovle(){cinn;for(int i1;in;i){int u,v,c;cinuvc;RG[u].push_back({v,c});RG[v].push_back({u,c});}predfs(1,0,0);int q;cinq;while(q--){cinm;m;d[1]1;for(int i2;im;i){cind[i];vis[d[i]]1;}build();coutDP(1)endl;for(int i2;im;i) vis[d[i]]0;//初始化部分很关键cnt0;}
}
int main()
{
#ifdef LOCALfreopen(in.txt, r, stdin);
#else// iosint t1;// cint;while(t--) sovle();
#endif // LOCALreturn 0;
}
