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卡在等待界面解决方法

MYSQL常用基本操作总结
SQL查询中各个关键字的执行先后顺序： from > on> join > where > group by > with > having >select
阅读更多2024-09-19
JAVA并发编程系列之Semaphore信号量剖析
候选人，心中万马奔腾！！！吐了一口82年老血，当场砸电脑回家！原因是：腾讯T2面试，现场限时3分钟+限最多20行代码，模拟地铁口安检进站。其中安检入口10个，当前排队人数是100个，每个人安检进站耗时
阅读更多2024-09-19
24年蓝桥杯及攻防世界赛题-MISC-2
24年蓝桥杯及攻防世界赛题-MISC-2
阅读更多2024-09-19
干货-并发编程提高——重谈 RUNNABLE-上篇（十四）
直接看它的 Javadoc 中的说明：一个在 JVM 中执行的线程处于这一状态中。（A threadexecuting而传统的进（线）程状态一般划分如下：注：这里的进程指早期的单线程进程，这里所谓进程
阅读更多2024-09-19
phpstudy 建站使用 php8版本打开 phpMyAdmin后台出现网页提示致命错误：（phpMyAdmin这是版本问题导致的）
将网站根目录phpMyAdmin4.8.5里面的文件换成官网下载的5.2.1版本即可。重启网站，打开phpMyAdmin后台即可（若打不开更改 mysql密码即可）解决方法：官网下载phpmyadm
阅读更多2024-09-19
零工市场小程序：保障灵活就业
截止2024年高校毕业生达到1179万，在今年的经济情况下，就业市场就面临着比较大的压力，许多毕业生面临一时之间难以找到合适的工作的问题，那么求职者就会需要一份临时的工作来得到报酬，面对传统的找零工方
阅读更多2024-09-19
Linux中权限和指令
mv指令是move的缩写，用来，经常用来备份文件或目录。
阅读更多2024-09-19
Redis 底层揭秘：事务与 Lua 脚本的工作原理
定义Lua 是一种轻量级的脚本语言，它可以在 Redis 中被执行，用于实现复杂的逻辑操作。优势与事务相比，Lua 脚本具有更高的性能和更好的灵活性。Lua 脚本可以在 Redis 服务器端一次性执行
阅读更多2024-09-19
Vue3使用shapefile读取矢量数据，以数组形式返回坐标点
【代码】Vue3使用shapefile读取矢量数据，以数组形式返回坐标点。
阅读更多2024-09-19
WEB 编程：使用富文本编辑器 Quill 配合 WebBroker 后端
评估了好几个，最后选择这个开源的。把前端代码，存储为一个单独的文本文件，方便随便哪个页面需要的时候可以使用。相当于封装为一个独立的对象，方便代码重用。
阅读更多2024-09-19

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

一开始的hdu代码：

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

cf的...

相关文章

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