Codeforces Round 221 (Div. 1) D和hdu的C题树上启发式合并

🕗 发布于 2024-07-24 05:48 算法

小总结：

hdu的题是点对，这和树上路径相似，也和点分治思想一样，都是考虑三种情况不经过根，一端是根，跨根，第一种情况又可以归到子树的二三情况，所以一般都是只需要考虑后面两种情况。

在dfs的时候，第一个for循环就是处理轻儿子子树的答案，由于是轻儿子，最后都会被keep=0的条件把内容清除，也就是res置零和线段树删点，所以在处理完轻儿子后，所有东西都是空的，等于还没进入dfs一样。

接下来是处理重儿子，这时候重儿子的信息是被保留的，因为keep=1，也就是说res存了重儿子的答案，线段树里存了重儿子的节点。记录了重儿子的贡献，我们还需要去记录轻儿子的贡献，因为之前都删光了。

在处理轻儿子的时候，我们会发现已经有重儿子的信息了。而重儿子子树是和轻儿子不一样的，也就是说其实这时候是处理跨树也就是跨根的情况。这时候轻儿子子树的信息是被保留的，也就是把信息都保存到了重儿子上。遍历一颗颗轻儿子子树，然后每次处理当前轻儿子和以前遍历过的所有子树的信息，也就是从这颗子树到别的所以子树去找跨子树点对了。

处理完跨根，还剩第二种情况。直接就让当前根节点和所有子树点算贡献，然后再将根节点add进去就好了。

有好多好多坑....

一开始一直debug...然后瞎改，弄了个add和calc合并起来的代码，ac了...后来好好看了下，发现合并起来的代码其实就是将第一种情况（不跨根）和跨根的情况一起算了，所以就不用加上所有子树的答案了。

cf那题和hdu我都用线段树维护信息了，作为我一发就ac的题应该没啥好说的，和上题差不多吧...也就是用一个线段树来维护各个数的个数（虽然数组就可以了）。离线处理一下，然后把超过k的答案直接求k到N（比给的数据大就行）的个数。这个和上面那题不一样，不需要分跨不跨根什么的，直接统计所有点就好了，所以直接都add，然后再查询一下就好了。

一开始的hdu代码：

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
const int mod=1e9+7;
#define fi first
#define se second

int n,val[N];
vector<int> ve[N];
int son[N],siz[N];
int dep[N];
int ans[N];
int res,flag;
struct tree{
int tr[N*4];
void modify(int p,int l,int r,int x,ll value){
if(l==r){
tr[p]+=value;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(p<<1,l,mid,x,value);
else modify(p<<1|1,mid+1,r,x,value);
tr[p]=tr[p<<1]+tr[p<<1|1];
}
int query(int p,int l,int r,int x,int y){
if(x<=l&&y>=r){
return tr[p];
}
int res=0;
int mid=(l+r)>>1;
if(x<=mid) res+=query(p<<1,l,mid,x,y);
if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);
return res;
}
}cnt,sum,pfsum;

void dfs1(int x,int f){
siz[x]=1;
dep[x]=dep[f]+1;
for(auto y:ve[x]){
if(y==f) 
continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])
son[x]=y;
}
}

//max*max-min*max
int croot,rt;
void calc(int u,int f,ll value){

int cntmin;
cntmin=cnt.query(1,1,N,1,val[u]);
int summ;
summ=sum.query(1,1,N,1,N);
int pfsummax;
pfsummax=pfsum.query(1,1,N,val[u]+1,N);
res+=value*val[u]*val[u]*cntmin;
res+=value*pfsummax;
res-=value*summ*val[u];

cnt.modify(1,1,N,val[u],value);//add操作在calc操作前后都可以，因为对自己对自己的贡献是0 
sum.modify(1,1,N,val[u],value*val[u]);
pfsum.modify(1,1,N,val[u],value*(val[u]*val[u]));
if(croot) return;
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
calc(v,u,value);
}
}

void dfs2(int u,int f,bool keep){
for(auto v:ve[u]){
if(v==f||v==son[u])
continue;
dfs2(v,u,0);
}
if(son[u]){
dfs2(son[u],u,1);
flag=son[u];
}
croot=0;
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
calc(v,u,1);//只操作 
}
flag=0; 
croot=1;//表示只修改根节点 
calc(u,f,1);
croot=0;
ans[u]+=res*2;
if(!keep){
calc(u,f,-1);
}
}
void solve(){
cin>>n;
for(int i=2;i<=n;i++){
int a,b;
cin>>a>>b;
ve[a].push_back(b);
ve[b].push_back(a);
}
for(int i=1;i<=n;i++)
cin>>val[i];
dfs1(1,0);
dfs2(1,0,1);
int t=0;
for(int i=1;i<=n;i++)
t^=ans[i];
cout<<t;
}
signed  main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}

hdu改：后来的代码改了一下，也把我的所有理解写在注释里了（别小看这几句....都是血的教训）

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
const int mod=1e9+7;
#define fi first
#define se second

int n,val[N];
vector<int> ve[N];
int son[N],siz[N];
int dep[N];
int ans[N];
int res,flag;
struct tree{
int tr[N*4];
void modify(int p,int l,int r,int x,ll value){
if(l==r){
tr[p]+=value;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(p<<1,l,mid,x,value);
else modify(p<<1|1,mid+1,r,x,value);
tr[p]=tr[p<<1]+tr[p<<1|1];
}
int query(int p,int l,int r,int x,int y){
if(x<=l&&y>=r){
return tr[p];
}
int res=0;
int mid=(l+r)>>1;
if(x<=mid) res+=query(p<<1,l,mid,x,y);
if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);
return res;
}
}cnt,sum,pfsum;

void dfs1(int x,int f){
siz[x]=1;
dep[x]=dep[f]+1;
for(auto y:ve[x]){
if(y==f) 
continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])
son[x]=y;
}
}

//max*max-min*max
int croot;

void calc(int u,int f,ll value){

int cntmin;
cntmin=cnt.query(1,1,N,1,val[u]);
int summ;
summ=sum.query(1,1,N,1,N);
int pfsummax;
pfsummax=pfsum.query(1,1,N,val[u]+1,N);
res+=value*val[u]*val[u]*cntmin;
res+=value*pfsummax;
res-=value*summ*val[u];

if(croot) return;
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
calc(v,u,value);
}
}
void add(int u,int f,ll value){

cnt.modify(1,1,N,val[u],value);
sum.modify(1,1,N,val[u],value*val[u]);
pfsum.modify(1,1,N,val[u],value*(val[u]*val[u]));

if(croot) return;
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
add(v,u,value);
}
}
void dfs2(int u,int f,bool keep){
for(auto v:ve[u]){
if(v==f||v==son[u])
continue;
dfs2(v,u,0);
ans[u]+=ans[v];//不能res，因为会影响后面的轻儿子 
}

if(son[u]){
dfs2(son[u],u,1);
flag=son[u];
//res=0;//res和ans[flag]重复，且res*2不等于ans[son]，因为ans是+=res*2，可能有不经过根子树的答案 
ans[u]+=ans[flag];//res存的应该是重儿子第一种情况，不经过根的贡献 
}
res=0;//res一定要赋值为0，因为这里的res存的只有跨根贡献，没有重儿子里的其他贡献 
croot=0;//表示修改整个子树 
for(auto v:ve[u]){
if(v==f||v==flag)
continue;
calc(v,u,1);//先算贡献再add 
add(v,u,1);
}
flag=0;//注意置0，让后面的keep可以删整颗子树 
croot=1;//表示只修改根节点 
calc(u,f,1);
add(u,f,1);
croot=0;//同flag置0作用 
ans[u]+=res*2;//在子树不经过根的ans[v]不用*2，因为在子树乘过了，新算的res要*2 
if(!keep){
//calc(u,f,-1);//算贡献的时候是正着for循环前面所有子树和当前子树算贡献 
add(u,f,-1);//删的时候是正着for循环与后面所有子树和当前子树删贡献，一样的总贡献 
res=0;//再calc一次tle了....果然线段树太慢了，反正都是让res变0，直接置0 
}
}
void solve(){
cin>>n;
for(int i=2;i<=n;i++){
int a,b;
cin>>a>>b;
ve[a].push_back(b);
ve[b].push_back(a);
}
for(int i=1;i<=n;i++)
cin>>val[i];
dfs1(1,0);
dfs2(1,0,1);
int t=0;
for(int i=1;i<=n;i++)
t^=ans[i];
cout<<t;
}
signed  main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}

cf的...

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
#define fi first
#define se second
 

struct tree{
int tr[N*4];
void modify(int p,int l,int r,int x,int value){
if(l==r){
tr[p]+=value;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(p<<1,l,mid,x,value);
else modify(p<<1|1,mid+1,r,x,value);
tr[p]=tr[p<<1]+tr[p<<1|1];
}
int query(int p,int l,int r,int x,int y){
if(x<=l&&y>=r){
return tr[p];
}
int mid=(l+r)>>1;
int res=0;
if(x<=mid) res+=query(p<<1,l,mid,x,y);
if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);
return res;
}
}sum,cnt;

int n,m;
struct node{
int id,k;
};
int c[N],ans[N];
vector<node> ask[N];
vector<int> e[N];
int siz[N],son[N];
int flag,croot;

void df(int x,int f){
siz[x]=1;
for(auto y:e[x]){
if(y==f) 
continue;
df(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])
son[x]=y;
}
}

void add(int x,int f,int value){
sum.modify(1,0,N,c[x],value);
int num=sum.query(1,0,N,c[x],c[x]);
cnt.modify(1,0,N,num,1);
cnt.modify(1,0,N,num-value,-1);
if(croot)
return;
for(auto y:e[x]){
if(y==f||y==flag)
continue;
add(y,x,value);
}
}

void dfs(int x,int f,bool keep){
for(auto y:e[x]){
if(y==f||y==son[x])
continue;
dfs(y,x,0);
}
if(son[x])
dfs(son[x],x,1),flag=son[x];
croot=0;
for(auto y:e[x]){
if(y==f||y==son[x])
continue;
add(y,x,1);
}
croot=1;
add(x,f,1);
croot=0;
for(auto [id,k]:ask[x]){
ans[id]=cnt.query(1,0,N,k,N);
}
flag=0;
if(!keep){
add(x,f,-1);
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=m;i++){
int u,k;
cin>>u>>k;
ask[u].push_back({i,k});
}
df(1,0);
dfs(1,0,1);
for(int i=1;i<=m;i++)
cout<<ans[i]<<endl;
}
signed  main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/qq_73631501/article/details/140649673

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：物联网架构之Hadoop
下一篇：Jenkins卡在等待界面解决方法

react 中 useCallback Hook 作用
在 React 函数组件中，每次组件重新渲染时，内部的函数都会被重新创建。
阅读更多2024-11-16
如何在项目中用elementui实现分页器功能
5.在需要用到分页器的组件像服务器发请求（实现按钮和页面跳转的绑定）这是 Element UI 库中的一个组件，用于创建分页器。3.在分页器组件接收参数。
阅读更多2024-11-16
命名空间（namespace）详解（一）
经查可知，头文件stdlib.h中包含了名为atof的函数，此时我们再定义atof的变量就会报错，那么如何解决这个问题呢？就有了命名空间的用法。
阅读更多2024-11-16
ssm102“魅力”繁峙宣传网站的设计与实现+vue(论文+源码)_kaic
目录摘要ABSTRACT第1章绪论1.1背景及意义1.2 国内外研究概况1.3 研究的内容第2章相关技术2.1 JSP技术介绍2.2 JAVA简介2.3 MyEclipse开发环境2.4 T
阅读更多2024-11-16
深度学习--卷积神经网络
一般认为，人对外界的认知是从局部到全局的，而图像的空间联系也是局部的像素联系较为紧密，而距离较远的像素相关性则较弱。用一个或者多个卷积核扫描照片，卷积核自带的参数就是权重，在同一个卷积核扫描的图层当中
阅读更多2024-11-16
go反射深入学习
reflect.ValueOf(&x) 将 x 的地址传递给 reflect.Value，这使得我们能够通过反射修改 x 的值。传递给 reflect.ValueOf() 的是 x 的值，而不
阅读更多2024-11-16
Git如何简单使用
GitGitlabGitLab和GitHub有什么区别？Gitlab简单使用Gitlab常用指令
阅读更多2024-11-16
动态规划-背包问题——[模版]完全背包问题
与01背包相同，这里的完全背包也是需要一个二维dp表来表示最大价值，具体如下。返回最后一个位置dp表的值。从上至下，每一行从左到右。
阅读更多2024-11-16
hhdb数据库介绍(9-14)
介绍hhdb的sql语法支持
阅读更多2024-11-16
初识算法 · 位运算(end)
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）还是和前文一样，通过三个部分介绍，题目解析，算法原理，算法编写来介绍。那么话不多说，进入主题吧！题目解析题目的要求十分简单，是让我们在
阅读更多2024-11-16

Codeforces Round 221 (Div. 1) D和hdu的C题 树上启发式合并

一开始的hdu代码：

hdu改：后来的代码改了一下，也把我的所有理解写在注释里了（别小看这几句....都是血的教训）

cf的...

相关文章

Codeforces Round 221 (Div. 1) D和hdu的C题树上启发式合并