Luogu P4427 [BJOI2018]求和
2024-09-25 11:08:39
这是一道巨狗题，我已无力吐槽为什么我怎么写都不过
我们对于这种无修改的边权题目有一个经典的树上差分套路：
\(ans=sum_x+sum_y-2\cdot sum_{LCA(x,y)}\)
这里的\(sum\)表示的是从根到这个点的边权前缀和
然后这里求的是点权，我们还是用一样的策略，就是树上查分后加上这个点的点权即可，即：
\(ans=sum_x+sum_y-2\cdot sum_{LCA(x,y)}+node_{LCA(x,y)}\)
然后我们发现\(1\le k\le 50\)，所以我们预处理出所有的幂次的情况然后LCA查找即可。
然后就我就先写了我比较熟悉的DFS序+RMQ，然后蜜汁RE90pts
DFS序+RMQ CODE
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const LL N=300005,P=25,mod=998244353;
struct edge
{
LL to,next;
}e[N<<1];
struct RMQ
{
LL x,num;
}f[N<<1][P];
LL head[N],dep[N],fir[N],n,m,k,cnt,tot,x,y,rt=1,s[N][55],node[N][55];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(LL x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline void add(LL x,LL y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void swap(LL &a,LL &b)
{
LL t=a; a=b; b=t;
}
inline void DFS(LL now,LL fa,LL d)
{
dep[now]=d; f[++tot][0].x=dep[now]; f[tot][0].num=now; fir[now]=tot;
for (register LL i=head[now];i^-1;i=e[i].next)
if (e[i].to^fa) DFS(e[i].to,now,d+1),f[++tot][0].x=dep[now],f[tot][0].num=now;
}
inline void reset(LL now,LL fa,LL k)
{
node[now][k]=(node[now][k-1]*dep[now])%mod; s[now][k]=(s[now][k]+node[now][k])%mod;;
for (register LL i=head[now];i^-1;i=e[i].next)
if (e[i].to^fa) s[e[i].to][k]=(s[e[i].to][k]+s[now][k])%mod,reset(e[i].to,now,k);
}
inline void init(void)
{
for (register LL j=1;j<P;++j)
for (register LL i=1;i+(1<<j)-1<=tot;++i)
f[i][j]=f[i][j-1].x<f[i+(1<<j-1)][j-1].x?f[i][j-1]:f[i+(1<<j-1)][j-1];
}
inline LL LCA(LL x,LL y)
{
x=fir[x]; y=fir[y]; if (x>y) swap(x,y);
LL k=(LL)log2(y-x+1);
return f[x][k].x<f[y-(1<<k)+1][k].x?f[x][k].num:f[y-(1<<k)+1][k].num;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register LL i; read(n);
memset(head,-1,sizeof(head));
memset(e,-1,sizeof(e));
for (i=1;i<n;++i)
read(x),read(y),add(x,y),add(y,x);
DFS(rt,-1,0); init();
for (i=1;i<=n;++i)
node[i][0]=1;
for (i=1;i<=50;++i)
reset(rt,-1,i); read(m);
while (m--)
{
read(x); read(y); read(k); LL fa=LCA(x,y);
write((LL)((s[x][k]+s[y][k]-(2*s[fa][k])%mod+node[fa][k])%mod+mod)%mod); putchar('\n');
}
return 0;
}
然后我就不爽了，直接上了大力树剖，当然很不幸，树剖被Hack数据卡掉了
大力树剖CODE
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=300005,K=55,mod=998244353;
struct edge
{
int to,next;
}e[N<<1];
int n,m,rt=1,x,y,k,cnt,tot,head[N],dep[N][K],tree[N<<2][K],father[N],id[N],top[N],son[N],size[N],num[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void swap(int &a,int &b)
{
int t=a; a=b; b=t;
}
inline void build(int k,int rt,int l,int r)
{
if (l==r)
{
tree[rt][k]=dep[num[l]][k];
return;
}
int mid=l+r>>1;
build(k,rt<<1,l,mid); build(k,rt<<1|1,mid+1,r);
tree[rt][k]=tree[rt<<1][k]+tree[rt<<1|1][k];
if (tree[rt][k]>=mod) tree[rt][k]-=mod;
}
inline int query(int k,int rt,int l,int r,int beg,int end)
{
if (l>=beg&&r<=end) return tree[rt][k];
int mid=l+r>>1,res=0;
if (beg<=mid) res+=query(k,rt<<1,l,mid,beg,end);
if (end>mid) res+=query(k,rt<<1|1,mid+1,r,beg,end);
if (res>=mod) res-=mod; return res;
}
inline void DFS1(int now,int fa,int d)
{
dep[now][1]=d; father[now]=fa; size[now]=1; int res=-1;
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=fa)
{
DFS1(e[i].to,now,d+1);
size[now]+=size[e[i].to];
if (size[e[i].to]>res) res=size[e[i].to],son[now]=e[i].to;
}
}
inline void DFS2(int now,int topf)
{
id[now]=++tot; num[tot]=now; top[now]=topf;
if (!son[now]) return; DFS2(son[now],topf);
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=father[now]&&e[i].to!=son[now]) DFS2(e[i].to,e[i].to);
}
inline void init(void)
{
for (register int i=1;i<=50;++i)
{
for (register int j=1;j<=n&&i!=1;++j)
dep[j][i]=(LL)dep[j][i-1]*dep[j][1]%mod;
build(i,1,1,n);
}
}
inline int get_sec(int k,int x,int y)
{
int ans=0;
while (top[x]!=top[y])
{
if (dep[top[x]][1]<dep[top[y]][1]) swap(x,y);
ans+=query(k,1,1,n,id[top[x]],id[x]);
if (ans>=mod) ans-=mod; x=father[top[x]];
}
if (dep[x][1]<dep[y][1]) swap(x,y);
ans+=query(k,1,1,n,id[y],id[x]);
if (ans>=mod) ans-=mod; return ans;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n);
memset(head,-1,sizeof(head));
memset(e,-1,sizeof(e));
for (i=1;i<n;++i)
read(x),read(y),add(x,y),add(y,x);
DFS1(rt,-1,0); DFS2(rt,rt); init(); read(m);
while (m--)
{
read(x); read(y); read(k);
write(get_sec(k,x,y)); putchar('\n');
}
return 0;
}
虽然100pts了，但是不解为什么过不了Hack数据。
算了不管明天用倍增这个传说中最稳定的算法搞一下，看看是不是我太非了。
Upt：倍增LCA不开O2轻松跑过......
我以后写LCA只用倍增！
CODE
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=300005,K=55,P=25,mod=998244353;
struct edge
{
int to,next;
}e[N<<1];
int head[N],father[N][P],n,m,x,y,k,rt=1,cnt;
LL sum[N][K],dep[N][K];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(LL x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void swap(int &a,int &b)
{
int t=a; a=b; b=t;
}
inline void rebuild(int now)
{
for (register int i=2;i<=50;++i)
dep[now][i]=dep[now][i-1]*dep[now][1]%mod;
for (register int i=1;i<=50;++i)
sum[now][i]=(dep[now][i]+sum[father[now][0]][i])%mod;
}
inline void DFS(int now,int fa,int d)
{
father[now][0]=fa; dep[now][1]=d; rebuild(now);
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=fa) DFS(e[i].to,now,d+1);
}
inline void init(void)
{
for (register int j=0;j<P-1;++j)
for (register int i=1;i<=n;++i)
if (father[i][j]) father[i][j+1]=father[father[i][j]][j];
}
inline int LCA(int x,int y)
{
if (dep[x][1]<dep[y][1]) swap(x,y);
for (register int i=P-1;i>=0;--i)
if (father[x][i]&&dep[father[x][i]][1]>=dep[y][1]) x=father[x][i];
if (!(x^y)) return x;
for (register int i=P-1;i>=0;--i)
if (father[x][i]&&father[y][i]&&father[x][i]!=father[y][i])
{
x=father[x][i];
y=father[y][i];
}
return father[x][0];
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n);
memset(head,-1,sizeof(head));
memset(e,-1,sizeof(e));
for (i=1;i<n;++i)
read(x),read(y),add(x,y),add(y,x);
DFS(rt,0,0); init(); read(m);
while (m--)
{
read(x); read(y); read(k);
int fa=LCA(x,y);
write((sum[x][k]+sum[y][k]+(LL)2*mod-sum[fa][k]-sum[father[fa][0]][k])%mod); putchar('\n');
}
return 0;
}
最新文章
- Linux内核笔记——内存管理之块内存分配
- ANDROID调用webservice带soapheader验证
- Vim 的 tab 设置
- openfire聊天消息记录插件关键代码
- 强大的JS数组
- CircleImageView 圆形图片头像实现
- ubuntu安装水星MW150US无线网卡8188eu驱动
- 没有IDE的日子
- python 竖排文本
- 【虚拟机】解决网络适配器没有 VirtualBox Host-Only Ethernet Adapter 问题
- grpc（二）记一次grpc debug--io.grpc.StatusRuntimeException: UNKNOWN
- Hive记录-配置远程连接（JAVA/beeline）
- 【Java并发核心三】CountDownLatch、CyclicBarrier及Phaser
- 2018-2019-2 《网络对抗技术》Exp1 PC平台逆向破解 Week3 20165211
- spring boot 打包可以运行，但是执行main方法不能运行
- uva10603-倒水问题-暴力枚举-隐式图搜索
- MySQL半同步主从.md
- 测试csscss层叠顺序
- 某考试 T3 sine
- js中标签字符串的拼接