【Luogu】 P5642 人造情感(emotion)

2023-10-28 22:44

本文主要是介绍【Luogu】 P5642 人造情感(emotion),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

点击打开链接

题目解法

考虑如何计算 f ( U ) f(U) f(U),我不知道如何能想到下面的解法

一个技巧是把路径挂在 l c a lca lca

我们令 f u f_{u} fu 表示完全包含在 u u u 的子树中的路径的最大独立集
考虑转移,记 s u m u = ∑ v ∈ s o n ( u ) f v sum_{u}=\sum\limits_{v\in son(u)}f_v sumu=vson(u)fv

  1. 如果 u u u 不在任何一条选中的路径上
    f u = s u m u f_u=sum_u fu=sumu
  2. u u u 在权值为 w w w 的路径 x → y x\to y xy
    考虑对于 x → u x\to u xu y → u y\to u yu 的路径分别考虑,先给出式子:
    f u = s u m u + w − ∑ q ∈ p a t h ( x , u ) 或 q ∈ p a t h ( y , u ) ( f q − s u m q ) f_u=sum_u+w-\sum\limits_{q\in path(x,u)\;或\;q\in path(y,u)}(f_q-sum_q) fu=sumu+wqpath(x,u)qpath(y,u)(fqsumq)
    需要减去 f q − s u m q f_q-sum_q fqsumq 是因为 p a t h ( x , y ) path(x,y) path(x,y) 上的点都不能被选在其他的路径上,而我们的状态天然契合 f q − s u m q f_q-sum_q fqsumq q q q 不在 q q q 子树路径上的方案数

上面的东西可以用 B I T BIT BIT 维护,具体来说,它需要实现单点加,链查,而因为遍历树的独特结构,所以我们可以把它变成子树加,单点查

同时我们需要另一个数组 g u g_u gu 表示 u u u 子树外的路径的最大独立集
继续考虑分类转移,我们这里考虑用 g u g_u gu 的答案推导 g v ( v ∈ s o n ( u ) ) g_v(v\in son(u)) gv(vson(u)) 的答案

  1. u u u 不在任何一条路径上
    g v = g u + s u m u − f v g_v=g_u+sum_u-f_v gv=gu+sumufv
  2. u u u 在权值为 w w w 的路径 x → y x\to y xy 上, x → y x\to y xy 不经过 v v v
    x , y x,y x,y l c a lca lca h h h
    不难得出这个式子:
    g v = g h + w + s u m h − ∑ q ∈ p a t h ( x , y ) ( f q − s u m q ) − f v g_v=g_h+w+sum_h-\sum\limits_{q\in path(x,y)}(f_q-sum_q)-f_v gv=gh+w+sumhqpath(x,y)(fqsumq)fv

上面的东西可以把树拍平成 d f s dfs dfs 序,然后线段树做,注意要特殊考虑 l c a = u lca=u lca=u 的情况

最后就可以考虑计算答案
暴力计算我在程序中用注释标出了,然后就是优化这个暴力,这个不算太难,注意一些细节即可

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) x&-x
#define pb push_back
using namespace std;
const int N=300100,P=998244353;
struct Lines{ int u,v,w;};
int n,m,ans;
int depth[N],up[N][20],siz[N];
int Ldfn[N],Rdfn[N],dfs_clock;
int f[N],sum[N];//f[u]:u子树内不交路径的权值之和
int g[N];//g[u]:u子树外不交路径的权值之和
int e[N<<1],ne[N<<1],h[N],idx;
vector<int> G[N];
vector<Lines> ln[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void predfs(int u,int fa){depth[u]=depth[fa]+1;Ldfn[u]=++dfs_clock,up[u][0]=fa;for(int i=h[u];~i;i=ne[i]) if(e[i]!=fa) G[u].pb(e[i]),predfs(e[i],u);Rdfn[u]=dfs_clock;
}
int get_lca(int x,int y){if(depth[x]>depth[y]) swap(x,y);for(int i=18;i>=0;i--) if(depth[up[y][i]]>=depth[x]) y=up[y][i];if(x==y) return x;for(int i=18;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];return up[x][0];
}
struct BIT{int tr[N];void inc(int x,int v){ for(;x<=n;x+=lowbit(x)) tr[x]+=v;}void add(int l,int r,int v){ inc(l,v),inc(r+1,-v);}int ask(int x){int res=0;for(;x;x-=lowbit(x)) res+=tr[x];return res;}
}BIT;
struct SGT{int seg[N<<2];void modify(int l,int r,int x,int pos,int v){if(l==r){ seg[x]=max(seg[x],v);return;}int mid=(l+r)>>1;if(mid>=pos) modify(l,mid,x<<1,pos,v);else modify(mid+1,r,x<<1^1,pos,v);seg[x]=max(seg[x<<1],seg[x<<1^1]);}int query(int l,int r,int x,int L,int R){if(L<=l&&r<=R) return seg[x];int mid=(l+r)>>1;if(mid>=L&&mid<R) return max(query(l,mid,x<<1,L,R),query(mid+1,r,x<<1^1,L,R));if(mid>=L) return query(l,mid,x<<1,L,R);return query(mid+1,r,x<<1^1,L,R);}void upd(int pos,int v){ modify(1,n,1,pos,v);}int ask(int l1,int r1,int l2,int r2){int ret=0;if(l1<l2) ret=max(ret,query(1,n,1,l1,l2-1));if(r2<r1) ret=max(ret,query(1,n,1,r2+1,r1));return ret;}
}sg;
void calc_f(int u){for(int v:G[u]) calc_f(v),sum[u]+=f[v];//u不在路径上f[u]=sum[u];//u在路径上for(auto &E:ln[u]){E.w+=sum[u]-BIT.ask(Ldfn[E.u])-BIT.ask(Ldfn[E.v]);f[u]=max(f[u],E.w);//单点加+链求和+dfs的性质->子树加,单点查,单log}BIT.add(Ldfn[u],Rdfn[u],f[u]-sum[u]);
}
void calc_g(int u){sort(ln[u].begin(),ln[u].end(),[&](Lines x,Lines y){ return x.w>y.w;});for(int v:G[u]){g[v]=g[u]+sum[u]-f[v];for(auto E:ln[u])if(get_lca(E.u,v)!=v&&get_lca(E.v,v)!=v){//u,v没有一端在v的子树中g[v]=max(g[v],E.w+g[u]-f[v]);break;}g[v]=max(g[v],sg.ask(Ldfn[u],Rdfn[u],Ldfn[v],Rdfn[v])-f[v]);}for(auto E:ln[u]) sg.upd(Ldfn[E.u],E.w+g[u]),sg.upd(Ldfn[E.v],E.w+g[u]);for(int v:G[u]) calc_g(v);
}
void calc_ans(int u){int res=0;for(int v:G[u]) calc_ans(v),res=(res+siz[u]*siz[v])%P,siz[u]+=siz[v];siz[u]++;ans-=(g[u]+f[u])%P*(2*res+2*siz[u]-1)%P;res=(2*(siz[u]-1)*(n-siz[u])%P+2*res+2*n-1)%P;ans+=(f[u]-sum[u])%P*res%P;ans=(ans%P+P)%P;
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
// int get_sum(int x,int y){
//     int lca=get_lca(x,y),res=0;
//     while(x!=lca) res+=f[x]-sum[x],x=up[x][0];
//     while(y!=lca) res+=f[y]-sum[y],y=up[y][0];
//     res+=f[lca]-sum[lca];
//     return res;
// }
signed main(){n=read(),m=read();memset(h,-1,sizeof(h));for(int i=1;i<n;i++){int x=read(),y=read();add(x,y),add(y,x);}predfs(1,-1);for(int j=1;j<=18;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];for(int i=1;i<=m;i++){int u=read(),v=read(),w=read();int lca=get_lca(u,v);ln[lca].pb({u,v,w});}calc_f(1),calc_g(1),calc_ans(1);ans=(ans+f[1]%P*n%P*n)%P;// for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)//     ans+=f[1]-g[get_lca(i,j)]-f[get_lca(i,j)]+get_sum(i,j);printf("%lld\n",ans);fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

这篇关于【Luogu】 P5642 人造情感(emotion)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/296461

相关文章

深度剖析AI情感陪伴类产品及典型应用 Character.ai

前段时间AI圈内C.AI的受够风波可谓是让大家都丈二摸不着头脑,连C.AI这种行业top应用都要找谋生方法了!投资人摸不着头脑,用户们更摸不着头脑。在这之前断断续续玩了一下这款产品,这次也是乘着这个风波,除了了解一下为什么这么厉害的创始人 Noam Shazeer 也要另寻他路,以及产品本身的发展阶段和情况! 什么是Character.ai? Character.ai官网:https://

FHQ Treap模版(luogu P3369)

FHQ Treap模版(自用),带注释 #include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,root,idx;struct node{int l,r;int val,key,size;}tr[N];int getnew(int v){tr[++idx].val=v;//权值tr[idx].key=rand(

基于人工智能的音乐情感分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 音乐情感分类是通过对音乐音频信号进行分析,识别出音乐传递的情感,如“愉快”、“悲伤”、“愤怒”等。该技术在音乐推荐、情感分析、电影配乐等领域具有广泛的应用。本文将介绍如何构建一个基于人工智能的音乐情感分类系统,包括环境准备、系统设计及代码实现。 2. 项

基于人工智能的情感分析系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 情感分析系统是自然语言处理中的重要应用之一,用于从文本中自动识别和分析用户情感,如“积极”、“消极”或“中立”等。本文将介绍如何构建一个基于人工智能的情感分析系统,涵盖环境准备、系统设计及代码实现。 2. 项目背景 在电商、社交媒体、客户反馈等领域,情

情感分析和语音分析的人工标注问题

目录 1. 半监督学习2. 无监督学习3. 迁移学习4. 弱监督学习5. 数据增强6. 众包标注7. 利用公开数据集8. 自监督学习总结 尽管人工标注是情感分析和语音分析中常用的高质量数据获取方法,但也存在一些替代方法或辅助方法,可以在某些情况下减少人工标注的需求或完全替代人工标注。这些方法包括半监督学习、无监督学习、迁移学习、以及利用已有的标注数据集等。 1. 半监督学习

基于人工智能的文本情感分析系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 文本情感分析是一种自然语言处理技术,用于识别和提取文本中的情感信息。该技术在市场分析、产品评价、社交媒体监控等领域具有广泛应用。本文介绍一个基于人工智能的文本情感分析系统,重点介绍环境准备、系统设计及实现。 2. 项目背景 随着社交媒体和电商平台的

复旦大学王龑团队发布《静态与动态情感的面部表情识别》综述

论文链接:https://arxiv.org/pdf/2408.15777 复旦大学,王龑博士后领衔,发布《静态与动态情感的面部表情识别》(A Survey on Facial Expression Recognition of Static and Dynamic Emotions)综述,对基于图像的静态面部表情识别(SFER)和基于视频的动态面部表情识别(DFER)方法进行了全面综述,从

情感分析——中文金融情感词典

情感分析——中文金融情感词典 [1]姜富伟,孟令超,唐国豪.媒体文本情绪与股票回报预测[J].经济学(季刊),2021,21(04):1323-1344.DOI:10.13821/j.cnki.ceq.2021.04.10. 该文章在Loughranand MacDonald(2011)词典的基础上通过人工筛选和Word2vec算法扩充,构建了一个更新更全面的中文金融情感词典。 需在尊

机器学习:基于机器学习的中文评论情感分析

通过机器学习技术对中文评论进行情感分析。我们使用了jieba进行中文分词,移除了停用词,并利用词袋模型(Bag of Words)和多项式朴素贝叶斯分类器对评论进行了情感分类。实验结果表明,该模型在测试集上达到了较高的准确率。 1.数据收集 我们收集了两组中文评论数据,分别代表正面(cp)和负面(hp)情感。 import pandas as pdcp=pd.read_table(r"./

基于机器学习的商品评论情感分析

从淘宝爬取评论 使用Selenium模拟真实登录行为,并爬取数据。 数据清理 如果文本中有“666“,”好好好“等无用词语,去掉评论中的标点符号。 分词 使用jieba精确模式进行分词,构造词典 将词汇向量化 创建词语字典,并返回每个词语的索引,词向量,以及每个句子所对应的词语索引 分类模型对比 SVM vs LSTM 近年来,随着互联网和电子商务的迅猛发展