常熟做网站的公司,专门做水生植物销售网站,网页制作与维护,漯河建设网站[SDOI2011]消耗战
题意#xff1a;
给出n个点的一棵带有边权的树,以及q个询问.每次询问给出k个点,询问这使得这k个点与1点不连通所需切断的边的边权和最小是多少.
题解#xff1a;
树型dp虚树 dp[x]:切断x及其子树上询问点的最小代价 预处理出minv[pos]代表从11到pos路径…[SDOI2011]消耗战
题意
给出n个点的一棵带有边权的树,以及q个询问.每次询问给出k个点,询问这使得这k个点与1点不连通所需切断的边的边权和最小是多少.
题解
树型dp虚树 dp[x]:切断x及其子树上询问点的最小代价 预处理出minv[pos]代表从11到pos路径上最小的边权 如果pos是询问点,dp(pos)minv[pos] 否则最小代价dp(pos)min(minv[pos],∑dp(to))其中to是pos的儿子 如果pos为询问点按理说不用dp[to]的值但是仍然要对其儿子进行dfs因为清空虚树需要对整个虚树进行遍历 如果对整个子树进行dp复杂度过高这时候就需要建虚树关于虚树见博文 建虚图
void insert(int x) {if(top 1) {s[top] x; return ;}int lca LCA(x, s[top]);if(lca s[top]) return ;//以为s[top]也是关键点那么s[top]子树里的点就没必要处理了 while(top 1 dfn[s[top - 1]] dfn[lca]) add_edge(s[top - 1], s[top]), top--;if(lca ! s[top]) add_edge(lca, s[top]), s[top] lca;//s[top] x;
}为什么(lca s[top]直接推出不把x加栈内 因为s[top]也是关键点x也是关键点x是s[top]的子树那根据题意如果将s[top]与根节点断开x节点自然也就断开了也就是我们只需要考虑s[top]即可x自动被考虑其中
代码
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#includecstdio
#includealgorithm
#includecstring
#includevector
#define getchar() (p1 p2 (p2 (p1 buf) fread(buf, 1, 1 21, stdin), p1 p2) ? EOF : *p1)
#define LL long long
char buf[(1 21) 1], *p1 buf, *p2 buf;
using namespace std;
const int MAXN 250001;
inline int read() {char c getchar(); int x 0, f 1;while(c 0 || c 9) {if(c -) f -1; c getchar();}while(c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}
char obuf[1 24], *Oobuf;
void print(LL x) {if(x 9) print(x / 10);*O x % 10 0;
}
int N, M;
struct Edge {int u, v, w, nxt;
}E[MAXN 1];
int head[MAXN], num 1;
inline void AddEdge(int x, int y, int z) {E[num] (Edge) {x, y, z, head[x]};head[x] num;
}
vectorint v[MAXN];
void add_edge(int x, int y) {v[x].push_back(y);
}
int a[MAXN], dfn[MAXN], topf[MAXN], siz[MAXN], son[MAXN], s[MAXN], top, deep[MAXN], fa[MAXN], ID 0;
LL mn[MAXN];
void dfs1(int x, int _fa) {siz[x] 1; fa[x] _fa;for(int i head[x]; i ! -1; i E[i].nxt) {if(E[i].v _fa) continue;deep[E[i].v] deep[x] 1;mn[E[i].v] min(mn[x], (LL)E[i].w);dfs1(E[i].v, x);siz[x] siz[E[i].v];if(siz[E[i].v] siz[son[x]]) son[x] E[i].v;}
}
void dfs2(int x, int topfa) {topf[x] topfa;dfn[x] ID;if(!son[x]) return ;dfs2(son[x], topfa);for(int i head[x]; i ! -1; i E[i].nxt) if(!topf[E[i].v]) dfs2(E[i].v, E[i].v);
}
int LCA(int x, int y) {while(topf[x] ! topf[y]) {if(deep[topf[x]] deep[topf[y]]) swap(x, y);x fa[topf[x]];}if(deep[x] deep[y]) swap(x, y);return y;
}
void insert(int x) {if(top 1) {s[top] x; return ;}int lca LCA(x, s[top]);if(lca s[top]) return ;//以为s[top]也是关键点那么s[top]子树里的点就没必要处理了 while(top 1 dfn[s[top - 1]] dfn[lca]) add_edge(s[top - 1], s[top]), top--;if(lca ! s[top]) add_edge(lca, s[top]), s[top] lca;//s[top] x;
}
LL DP(int x) {if(v[x].size() 0) return mn[x];LL sum 0;for(int i 0; i v[x].size(); i) sum DP(v[x][i]);v[x].clear();return min(sum, (LL)mn[x]);
}
int comp(const int a, const int b) {return dfn[a] dfn[b];
}
int main() {memset(head, -1, sizeof(head));//memset(mn, 0xff, sizeof(mn));mn[1] 1ll 60;N read();for(int i 1; i N - 1; i) {int x read(), y read(), z read();AddEdge(x, y, z); AddEdge(y, x, z);}deep[1] 1;dfs1(1, 0);dfs2(1, 1);M read();/*for(int i 1; i N; i) for(int j 1; j N; j)printf(%d %d %d\n, i, j, LCA(i, j));*///for(int i 1; i N; i) printf(%d , mn[i]); puts();while(M--) {int K read();for(int i 1; i K; i) a[i] read();sort(a 1, a K 1, comp);s[top 1] 1;for(int i 1; i K; i) insert(a[i]);while(top 0) add_edge(s[top - 1], s[top]), top--;print(DP(1)), *O \n; }fwrite(obuf, O-obuf, 1 , stdout); return 0;
}
