提供手机自适应网站建设维护,网站设计培训成都,果洛营销网站建设哪家好,网站前台后台模板下载传送门
[前题提要]:无
题目描述:
就是给你一棵树,然后每个点有花费,然后你可以选一个点,付费后对这个点的子树的所有叶子结点增减任意权值.
考虑有一个人会给这棵树的所有叶子结点赋值(值我们不知道),输出最小的花费,使得无论它如何赋值,我们使用上述的花
费都能使所有的叶子…传送门
[前题提要]:无
题目描述:
就是给你一棵树,然后每个点有花费,然后你可以选一个点,付费后对这个点的子树的所有叶子结点增减任意权值.
考虑有一个人会给这棵树的所有叶子结点赋值(值我们不知道),输出最小的花费,使得无论它如何赋值,我们使用上述的花
费都能使所有的叶子节点变为0考虑对一个点的子树的所有叶子节点进行增减任意值.不难联想到对一个点的子树的所有节点增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改. 考虑记录一个点的所有叶子节点,并且按照 d f s dfs dfs序将其离散化存下.按照 d f s dfs dfs序的性质,我们会发现一个点的所有叶子节点必然是连续的区间.那么此时我们的问题就变成了: 给你 n n n个可以修改的区间,每一个区间都有其修改范围,修改每一个区间需要一定花费,问你至少需要多少花费将所有数字变为0 考虑到区间修改以及单点查询,我们想到使用差分来解决.假设我们使用一个差分数组 k [ i ] a [ i ] − a [ i − 1 ] k[i]a[i]-a[i-1] k[i]a[i]−a[i−1],那么对于每一次区间修改来说,我们都是 a [ l ] v a l , a [ r 1 ] − v a l a[l]val,a[r1]-val a[l]val,a[r1]−val,那么最终我们需要得到的所有的 k [ i ] 0 k[i]0 k[i]0. 此时有一个巧妙的转化,考虑我们需要所有的k[i]变为0,但是显然我们的差分数组是不改变前缀和的,所以此时所有的值肯定都转移到了cnt1的位置(假设我们有cnt个叶子节点),那么对于我们的数的转移来说,我们只能将 l l l转移到 r 1 r1 r1,如果我们将转移过程看成边,将每一个叶子结点看成点,那么我们想将所有的值都转移到 c n t 1 cnt1 cnt1,就需要所有的点都联通才行,这样才能保证无论怎么赋值我们都可以将其转移到 c n t 1 cnt1 cnt1的位置 那么此时这道题就简单了,考虑到必须所有点都联通,每次选择联通一个点我们都需要花费,又需要花费最小,所以显然是个最小生成树的模型,此时使用最小生成树跑一下就行.
但是还有一个问题,那就是这道题的最终问题是所有的可能性的最小生成树的点,所以我们用朴素的 k r u s k a l kruskal kruskal跑出来的只是一棵树,需要改一下.考虑到最小生成树的性质,当边相同时,我们可以选择任意一条不在联通块中的边,所以这些边显然都是平等的,所以这些边都是我们的答案(当然这一点是可以严谨证明的,但是限于篇幅,此处不再赘述) 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100);
}
#define maxn 1000000
#define int long long
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int w[maxn];vectorintedge[maxn];int l[maxn],r[maxn];
int cnt0;
void dfs(int u,int per_u) {if(edge[u].size()1u!1) {cnt;l[u]r[u]cnt;}for(auto v:edge[u]) {if(vper_u) continue;dfs(v,u);l[u]min(l[u],l[v]);r[u]max(r[u],r[v]);}
}
struct Edge{int u,v,w,id;bool operator (const Edge rhs) const {return wrhs.w;}
}edge2[maxn];
int fa[maxn];
int find(int x) {if(xfa[x]) return x;else return fa[x]find(fa[x]);
}
signed main() {int nread();for(int i1;in;i) {w[i]read();}for(int i1;in;i) {int uread();int vread();edge[u].push_back(v);edge[v].push_back(u);}memset(l,0x3f,sizeof l);memset(r,-0x3f,sizeof r);dfs(1,0);for(int i1;in;i) {int ul[i],vr[i];edge2[i]{u,v1,w[i],i};}for(int i1;icnt;i) fa[i]i;sort(edge21,edge21n);vectorintans;int this_cnt0;int need0;for(int i1;in;i) {int ri;while(r1nedge2[r1].wedge2[r].w) r;for(int ji;jr;j) {auto [u,v,w,k]edge2[j];if(find(u)!find(v)) {this_cnt;ans.push_back(k);}}for(int ji;jr;j) {auto [u,v,w,k]edge2[j];if(find(u)!find(v)) {needw;fa[find(u)]find(v);}}ir;}sort(ans.begin(),ans.end());coutneed ans.size()endl;for(auto i:ans) couti ;return 0;
}
