bzoj3052
2024-10-30 19:42:09
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3052
题目大意:自己看看,懒得写
题解:带修改的树上莫队,经典爆评测机的题
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 100100
#define ll long long
using namespace std;
int n,m,q,blo;
ll ans;
int tot,top,totc,totq,lydsytime,belong;
int bin[],deep[maxn],fa[maxn][],dfn[maxn];
int z[maxn];
int num[maxn];
int now[maxn],v[maxn*],pre[maxn*];
int pos[maxn];
ll res[maxn],val[maxn],c[maxn],cpre[maxn],w[maxn];
bool vis[maxn];
struct data{
int x,y,t,id;
ll pre;
}cg[maxn],bg[maxn];
int read()
{
int x=; char ch; bool bo=;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') bo=;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
if (bo) return -x; return x;
}
bool cmp(data a,data b)
{
if (pos[a.x]==pos[b.x]) return dfn[a.y]<dfn[b.y]; return pos[a.x]<pos[b.x];
}
void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
void prework(){
bin[]=;
for (int i=; i<=; i++) bin[i]=bin[i-]*;
}
int dfs(int x)
{
int size=;
dfn[x]=++lydsytime;
for (int i=; i<=; i++)
if (deep[x]>=bin[i])
fa[x][i]=fa[fa[x][i-]][i-];
else
break;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (son==fa[x][]) continue;
deep[son]=deep[x]+;
fa[son][]=x;
size+=dfs(son);
if (size>blo)
{
belong++;
for (int i=; i<=blo; i++) pos[z[top--]]=belong;
size=;
}
}
z[++top]=x;
return size+;
}
int lca(int x,int y)
{
// cout<<" pre "<<x<<" "<<y<<endl;
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for (int i=; bin[i]<=t; i++)
if (bin[i]&t)
x=fa[x][i];
for (int i=; i>=; i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i], y=fa[y][i];
// cout<<" now "<<x<<" "<<y<<endl;
if (x==y) return x;
return fa[x][];
}
void reverse(int x)
{
//cout<<" re "<<x<<" "<<c[x]<<" "<<val[c[x]]<<" "<<num[c[x]]<<" "<<w[num[c[x]]+1]<<" "<<w[1]<<endl;
if (vis[x]) ans-=val[c[x]]*w[num[c[x]]],num[c[x]]--;
else num[c[x]]++,ans+=val[c[x]]*w[num[c[x]]];
vis[x]^=;
}
void work(int u,int v)
{
//cout<<" pre u v "<<u<<" "<<v<<endl;
while (u!=v)
{
if (deep[u]>deep[v])
{
reverse(u);
u=fa[u][];
}
else
{
reverse(v);
v=fa[v][];
}
//cout<<" now u v "<<u<<" "<<v<<" "<<endl;
}
}
void change(int x,int y)
{
if (vis[x])
{
reverse(x);
c[x]=y;
reverse(x);
}
else c[x]=y;
}
void init()
{
n=read(); m=read(); q=read();
blo=pow(n,2.0/)*0.5;
for (int i=; i<=m; i++) val[i]=read();
for (int i=; i<=n; i++) w[i]=read();
for (int i=; i<n; i++)
{
int u=read(),v=read();
ins(u,v); ins(v,u);
}
dfs();
//for (int i=1; i<=n; i++) cout<<" dsdsd "<<fa[i][0]<<" "<<dfn[i]<<endl;
belong++;
while (top) pos[z[top--]]=belong;
for (int i=; i<=n; i++) c[i]=cpre[i]=read();
for (int i=; i<=q; i++)
{
int type=read(),x=read(),y=read();
if (!type)
{
totc++; cg[totc].x=x,cg[totc].y=y,cg[totc].pre=cpre[x],cpre[x]=y;
}
else
{
totq++; bg[totq].x=x,bg[totq].y=y,bg[totq].t=totc; bg[totq].id=totq;
}
}
sort(bg+,bg+totq+,cmp);
/*for (int i=1; i<=totq; i++)
{
cout<<" "<<bg[i].x<<" "<<bg[i].y<<" "<<bg[i].t<<" "<<endl;
}*/
}
void solve()
{
for (int i=; i<=bg[].t; i++) change(cg[i].x,cg[i].y);
work(bg[].x,bg[].y);
int t=lca(bg[].x,bg[].y);
//cout<<" "<<t<<" "<<bg[1].x<<" "<<bg[1].y<<endl;
reverse(t); res[bg[].id]=ans; reverse(t);
for (int i=; i<=totq; i++)
{
for (int j=bg[i-].t+; j<=bg[i].t; j++)
change(cg[j].x,cg[j].y);
for (int j=bg[i-].t+; j>bg[i].t; j--)
change(cg[j].x,cg[j].pre);
work(bg[i-].x,bg[i].x); work(bg[i-].y,bg[i].y);
int t=lca(bg[i].x,bg[i].y);
reverse(t); res[bg[i].id]=ans; reverse(t);
}
}
int main()
{
prework();
init();
solve();
for (int i=; i<=totq; i++)
printf("%lld\n",res[i]);
}
/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/
一次CE,一次WA,一次AC
-------------哦,对了这道题还是有个坑,就是怎么推出带修改的树上莫队时间复杂度!待zfy来教我补!
最新文章
- iOS开发之Socket
- How Google Tests Software - The Life of a TE
- PHP发短信 PEAR 包:Services_Sms
- Java Hello World例子和添加按钮事件与功能
- Linux内核源码详解——命令篇之iostat[zz]
- Porter/Duff,图片加遮罩setColorFilter
- 企业用户2T(含秒传),普通用户20G
- java图片缩放
- TortoiseGit - 分支管理 -增加分支
- ArcGIS制图表达Representation-规则和几何效果
- ch1-vuejs基础入门(hw v-bind v-if v-for v-on v-model 应用组件简介 小案例)
- Python之上下文管理
- less简述
- java.util.HashSet, java.util.LinkedHashMap, java.util.IdentityHashMap 源码阅读 (JDK 1.8)
- javascript模块化编程 从入门到实战
- 记一次Springboot启动异常
- 通过C# WinForm控件创建的WPF WIndow窗口控件无法输入的问题
- odoo返写数据
- 有了#ifdef 为什么还需要#if defined
- 转换python脚本为可执行程序的方式