[樹上莫隊]BZOJ 3757 3052 4129
12212 ワード
コンベヤー？ドア
http://blog.csdn.net/kuribohG/article/details/41458639
http://vfleaking.blog.163.com/blog/static/174807634201311011201627/
「
S（v，u）でvからuへの経路上の結点の集合を表す。
rootで根結点を表し、lca（v，u）でv、uの最近の先祖を表します。
では
S(v，u)=S(root，v)xor S(root，u)xor lca(v，u)
その中でx orは集合の対称性の差です。
簡単に言うと、ノードが二回消えます。
lcaは嫌いです。そこで定義します。
T(v，u)=S(root，v)xor S(root，u)
curVをtarget V前後T（curV，curU）変化に移動させることを観察した：
T(curV，curU)=S(root，curV)xor S(root，curU)
T(targtV，curU)=S(root，targtV)xor S(root，curU)
対称性の差を取る:
T(curV，curU)xor T(targtV，curU)=(S(root，curV)xor S(root，curU)xor(S(root，targtV)xor S(root，curU)
対称性が悪いための交換律、結合律：
T(curV，curU)xor T(targtV，curU)=S(root，curV)xorS(root，tagetV)
両側同時X or T(curV，curU)：
T(targtV，curU)= T(curV，curU)xor S(root，curV)xor S(root，targtV)
最後の二つがすっきりしています。
T(targtV，curU)= T(curV，curU)xor T(curV， ターゲットV
（公式恐怖症がある人は行かないでください。TuT）
つまり、更新するときは、xor T(curV) targtV)だけでいいです。
つまり、curVからtarget Vパス（CrV、targtVを除く）上の結点に対して、それらの存在性を逆に取れば良い。
」
——vfkブログ
BZOJ 3757
裸の木に列を作ってはいけない
改変樹をつけて列に並ぶな。
暴力の時間前に逆流する
ブロックN^(2/3)
ブロック分けて照会する
http://blog.csdn.net/kuribohG/article/details/41458639
http://vfleaking.blog.163.com/blog/static/174807634201311011201627/
「
S（v，u）でvからuへの経路上の結点の集合を表す。
rootで根結点を表し、lca（v，u）でv、uの最近の先祖を表します。
では
S(v，u)=S(root，v)xor S(root，u)xor lca(v，u)
その中でx orは集合の対称性の差です。
簡単に言うと、ノードが二回消えます。
lcaは嫌いです。そこで定義します。
T(v，u)=S(root，v)xor S(root，u)
curVをtarget V前後T（curV，curU）変化に移動させることを観察した：
T(curV，curU)=S(root，curV)xor S(root，curU)
T(targtV，curU)=S(root，targtV)xor S(root，curU)
対称性の差を取る:
T(curV，curU)xor T(targtV，curU)=(S(root，curV)xor S(root，curU)xor(S(root，targtV)xor S(root，curU)
対称性が悪いための交換律、結合律：
T(curV，curU)xor T(targtV，curU)=S(root，curV)xorS(root，tagetV)
両側同時X or T(curV，curU)：
T(targtV，curU)= T(curV，curU)xor S(root，curV)xor S(root，targtV)
最後の二つがすっきりしています。
T(targtV，curU)= T(curV，curU)xor T(curV， ターゲットV
（公式恐怖症がある人は行かないでください。TuT）
つまり、更新するときは、xor T(curV) targtV)だけでいいです。
つまり、curVからtarget Vパス（CrV、targtVを除く）上の結点に対して、それらの存在性を逆に取れば良い。
」
——vfkブログ
BZOJ 3757
裸の木に列を作ってはいけない
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define V G[p].v
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
struct edge{
int u,v;
int next;
};
edge G[100005];
int head[50005],inum=1;
inline void add(int u,int v,int p)
{
G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
int n,m,B,rt;
int c[50005];
int clk,pre[50005],depth[50005],parent[50005][20];
inline void dfs(int u,int fa)
{
pre[u]=++clk;
depth[u]=depth[fa]+1; parent[u][0]=fa;
for (int k=1;k<=18;k++)
parent[u][k]=parent[parent[u][k-1]][k-1];
for (int p=head[u];p;p=G[p].next)
if (V!=fa)
dfs(V,u);
}
int Stk[50005],top;
int bot,pos[50005];
inline void find(int u,int fa)
{
int last=top;
for (int p=head[u];p;p=G[p].next)
if (V!=fa)
{
find(V,u);
if (top-last>=B)
{
++bot;
while (top!=last) pos[Stk[top--]]=bot;
}
}
Stk[++top]=u;
}
inline int LCA(int u,int v)
{
if (depth[u]<depth[v]) swap(u,v);
for (int k=18;k>=0;k--)
if (((depth[u]-depth[v])>>k)&1)
u=parent[u][k];
if (u==v) return u;
for (int k=18;k>=0;k--)
if (parent[u][k]!=parent[v][k])
u=parent[u][k],v=parent[v][k];
return parent[u][0];
}
struct que{
int u,v,a,b;
int idx;
}Q[100005];
inline bool cmp(que A,que B)
{
return pos[A.u]==pos[B.u]?pre[A.v]<pre[B.v]:pos[A.u]<pos[B.u];
}
int vst[50005];
int cnt[50005];
int tot;
inline void Rev(int x)
{
if (!vst[x])
{
vst[x]=1,cnt[c[x]]++; if (cnt[c[x]]==1) tot++;
}
else
{
vst[x]=0,cnt[c[x]]--; if (cnt[c[x]]==0) tot--;
}
}
inline void T(int u,int v)
{
while (u!=v)
if (depth[u]<depth[v])
Rev(v),v=parent[v][0];
else
Rev(u),u=parent[u][0];
}
int ans[100005];
inline void Solve()
{
int lca;
T(Q[1].u,Q[1].v);
lca=LCA(Q[1].u,Q[1].v);
Rev(lca);
ans[Q[1].idx]=tot;
if (Q[1].a!=Q[1].b && cnt[Q[1].a] && cnt[Q[1].b]) ans[Q[1].idx]--;
Rev(lca);
for (int i=2;i<=m;i++)
{
T(Q[i].u,Q[i-1].u);
T(Q[i].v,Q[i-1].v);
lca=LCA(Q[i].u,Q[i].v);
Rev(lca);
ans[Q[i].idx]=tot;
if (Q[i].a!=Q[i].b && cnt[Q[i].a] && cnt[Q[i].b]) ans[Q[i].idx]--;
Rev(lca);
}
}
int main()
{
int _u,_v;
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
read(n); read(m);
for (int i=1;i<=n;i++)
read(c[i]);
for (int i=1;i<=n;i++)
{
read(_u),read(_v);
if (!_u) rt=_v;
else if (!_v) rt=_u;
else add(_u,_v,++inum),add(_v,_u,++inum);
}
dfs(rt,0);
B=sqrt(n);
find(rt,0);
while (top) pos[Stk[top--]]=bot;
for (int i=1;i<=m;i++)
{
read(Q[i].u); read(Q[i].v); read(Q[i].a); read(Q[i].b); Q[i].idx=i;
if (pre[Q[i].u]>pre[Q[i].v]) swap(Q[i].u,Q[i].v);
}
sort(Q+1,Q+m+1,cmp);
Solve();
for (int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}改変樹をつけて列に並ぶな。
暴力の時間前に逆流する
ブロックN^(2/3)
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define V G[p].v
using namespace std;
typedef long long ll;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
struct edge{
int u,v;
int next;
};
edge G[200005];
int head[100005],inum=1;
inline void add(int u,int v,int p)
{
G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
int n,m,_q,B;
int _V[100005],W[100005],C[100005];
int clk,pre[100005],depth[100005],parent[100005][21];
inline void dfs(int u,int fa)
{
pre[u]=++clk;
depth[u]=depth[fa]+1; parent[u][0]=fa;
for (int k=1;k<=20;k++)
parent[u][k]=parent[parent[u][k-1]][k-1];
for (int p=head[u];p;p=G[p].next)
if (V!=fa)
dfs(V,u);
}
int Stk[100005],top;
int bot,pos[100005];
inline void find(int u,int fa)
{
int last=top;
for (int p=head[u];p;p=G[p].next)
if (V!=fa)
{
find(V,u);
if (top-last>=B)
{
++bot;
while (top!=last) pos[Stk[top--]]=bot;
}
}
Stk[++top]=u;
}
inline int LCA(int u,int v)
{
if (depth[u]<depth[v]) swap(u,v);
for (int k=20;k>=0;k--)
if (((depth[u]-depth[v])>>k)&1)
u=parent[u][k];
if (u==v) return u;
for (int k=20;k>=0;k--)
if (parent[u][k]!=parent[v][k])
u=parent[u][k],v=parent[v][k];
return parent[u][0];
}
struct que{
int u,v,t;
int idx;
}Q[100005];
int cnt1;
inline bool cmp(que A,que B)
{
return pos[A.u]==pos[B.u]?pre[A.v]<pre[B.v]:pos[A.u]<pos[B.u];
}
struct chg{
int x,y,t;
int pre;
}X[100005];
int cnt2;
int ihead[100005];
ll ans[100005];
ll ret;
int vst[100005];
int cnt[100005];
inline void Rev(int x)
{
if (vst[x])
{
vst[x]=0; ret-=(ll)W[cnt[C[x]]]*_V[C[x]]; cnt[C[x]]--;
}
else
{
vst[x]=1; cnt[C[x]]++; ret+=(ll)W[cnt[C[x]]]*_V[C[x]];
}
}
inline void T(int u,int v)
{
while (u!=v)
if (depth[u]<depth[v])
Rev(v),v=parent[v][0];
else
Rev(u),u=parent[u][0];
}
inline void change(int x,int y)
{
if (vst[x])
{
Rev(x); C[x]=y; Rev(x);
}
else
C[x]=y;
}
inline void Solve()
{
int lca;
for (int i=1;i<=Q[1].t;i++)
change(X[i].x,X[i].y);
T(Q[1].u,Q[1].v);
lca=LCA(Q[1].u,Q[1].v);
Rev(lca);
ans[Q[1].idx]=ret;
Rev(lca);
for (int i=2;i<=cnt1;i++)
{
for (int j=Q[i-1].t+1;j<=Q[i].t;j++)
change(X[j].x,X[j].y);
for (int j=Q[i-1].t;j>Q[i].t;j--)
change(X[j].x,X[j].pre);
T(Q[i-1].u,Q[i].u);
T(Q[i-1].v,Q[i].v);
lca=LCA(Q[i].u,Q[i].v);
Rev(lca);
ans[Q[i].idx]=ret;
Rev(lca);
}
}
int main()
{
int _u,_v,order;
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
read(n); read(m); read(_q);
for (int i=1;i<=m;i++) read(_V[i]);
for (int i=1;i<=n;i++) read(W[i]);
for (int i=1;i<n;i++)
{
read(_u); read(_v);
add(_u,_v,++inum); add(_v,_u,++inum);
}
dfs(1,0);
B=pow(n,2.0/3);
find(1,0);
while (top) pos[Stk[top--]]=bot;
for (int i=1;i<=n;i++) read(C[i]),ihead[i]=C[i];
for (int i=1;i<=_q;i++)
{
read(order); read(_u); read(_v);
if (!order)
{
X[++cnt2].x=_u; X[cnt2].y=_v; X[cnt2].t=i; X[cnt2].pre=ihead[_u]; ihead[_u]=_v;
}
else
{
Q[++cnt1].u=_u; Q[cnt1].v=_v; Q[cnt1].t=cnt2; Q[cnt1].idx=cnt1;
if (pre[Q[cnt1].u]>pre[Q[cnt1].v]) swap(Q[cnt1].u,Q[cnt1].v);
}
}
sort(Q+1,Q+cnt1+1,cmp);
Solve();
for (int i=1;i<=cnt1;i++)
printf("%lld
",ans[i]);
return 0;
}
ブロック分けて照会する
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define V G[p].v
using namespace std;
typedef long long ll;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
struct edge{
int u,v;
int next;
};
edge G[100005];
int head[50005],inum=1;
inline void add(int u,int v,int p)
{
G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
int n,m,_q,B;
int C[50005];
int clk,pre[50005],depth[50005],parent[50005][21];
inline void dfs(int u,int fa)
{
pre[u]=++clk;
depth[u]=depth[fa]+1; parent[u][0]=fa;
for (int k=1;k<=20;k++)
parent[u][k]=parent[parent[u][k-1]][k-1];
for (int p=head[u];p;p=G[p].next)
if (V!=fa)
dfs(V,u);
}
int Stk[50005],top;
int bot,pos[50005];
inline void find(int u,int fa)
{
int last=top;
for (int p=head[u];p;p=G[p].next)
if (V!=fa)
{
find(V,u);
if (top-last>=B)
{
++bot;
while (top!=last) pos[Stk[top--]]=bot;
}
}
Stk[++top]=u;
}
inline int LCA(int u,int v)
{
if (depth[u]<depth[v]) swap(u,v);
for (int k=20;k>=0;k--)
if (((depth[u]-depth[v])>>k)&1)
u=parent[u][k];
if (u==v) return u;
for (int k=20;k>=0;k--)
if (parent[u][k]!=parent[v][k])
u=parent[u][k],v=parent[v][k];
return parent[u][0];
}
struct que{
int u,v,t;
int idx;
}Q[50005];
int cnt1;
inline bool cmp(que A,que B)
{
return pos[A.u]==pos[B.u]?pre[A.v]<pre[B.v]:pos[A.u]<pos[B.u];
}
struct chg{
int x,y,t;
int pre;
}X[50005];
int cnt2;
int ihead[50005];
namespace Block{
int pos[50015];
int cnt[50015];
int btot,sum[50015],size[50015];
int n,block;
inline void init(int _n){
n=_n+5;
block=sqrt(n);
for (int i=1;i<=n;i++)
pos[i]=(i-1)/block+1,size[pos[i]]++;
btot=pos[n];
}
inline void add(int x,int r)
{
x++;
if (x>n) return;
if (r==1)
{
cnt[x]++;
if (cnt[x]==1)
sum[pos[x]]++;
}
else
{
cnt[x]--;
if (cnt[x]==0)
sum[pos[x]]--;
}
}
inline int query()
{
for (int i=1;i<=btot;i++)
if (sum[i]!=size[i])
for (int j=(i-1)*block+1;;j++)
if (!cnt[j])
return j-1;
}
}
int vst[50005];
inline void Rev(int x)
{
if (!vst[x])
{
vst[x]=1; Block::add(C[x],1);
}
else
{
vst[x]=0; Block::add(C[x],-1);
}
}
inline void T(int u,int v)
{
while (u!=v)
if (depth[u]>depth[v])
Rev(u),u=parent[u][0];
else
Rev(v),v=parent[v][0];
}
inline void Change(int x,int y)
{
if (vst[x])
{
Rev(x); C[x]=y; Rev(x);
}
else C[x]=y;
}
int ans[50005];
inline void Solve()
{
Block::init(n);
int lca;
for (int i=1;i<=Q[1].t;i++)
Change(X[i].x,X[i].y);
T(Q[1].u,Q[1].v);
lca=LCA(Q[1].u,Q[1].v);
Rev(lca);
ans[Q[1].idx]=Block::query();
Rev(lca);
for (int i=2;i<=cnt1;i++)
{
for (int j=Q[i-1].t+1;j<=Q[i].t;j++)
Change(X[j].x,X[j].y);
for (int j=Q[i-1].t;j>Q[i].t;j--)
Change(X[j].x,X[j].pre);
T(Q[i-1].u,Q[i].u);
T(Q[i-1].v,Q[i].v);
lca=LCA(Q[i].u,Q[i].v);
Rev(lca);
ans[Q[i].idx]=Block::query();
Rev(lca);
}
}
int main()
{
int _u,_v,order;
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
read(n); read(m);
for (int i=1;i<=n;i++)
read(C[i]),ihead[i]=C[i];
for (int i=1;i<n;i++)
{
read(_u); read(_v);
add(_u,_v,++inum); add(_v,_u,++inum);
}
dfs(1,0);
B=pow(n,2.0/3);
find(1,0);
while (top) pos[Stk[top--]]=bot;
for (int i=1;i<=m;i++)
{
read(order); read(_u); read(_v);
if (!order)
{
X[++cnt2].x=_u; X[cnt2].y=_v; X[cnt2].t=i; X[cnt2].pre=ihead[_u]; ihead[_u]=_v;
}
else
{
Q[++cnt1].u=_u; Q[cnt1].v=_v; Q[cnt1].t=cnt2; Q[cnt1].idx=cnt1;
if (pre[Q[cnt1].u]>pre[Q[cnt1].v]) swap(Q[cnt1].u,Q[cnt1].v);
}
}
sort(Q+1,Q+cnt1+1,cmp);
Solve();
for (int i=1;i<=cnt1;i++)
printf("%d
",ans[i]);
return 0;
}