数据结构乱做
HJWJBSR
posted @ 2016年1月16日 09:16
in 题解
, 654 阅读
最近在补课件上一些题目。就只放CLS的一些题目上来好了。。
感觉这些题做起来真是要死。毕竟代码能力弱都要调好久= =做到后面感觉到了深深的绝望。
本来还想开坑Sone1，而且本来想写课件上面给出的LCT套ETT的做法，但是n log^2 n，10w范围，40s时限，常数还这么大。感觉很不资瓷的样子所以写了一半细思之下就退坑了。
BZOJ4068 [CTSC2015] App：首先显然这是个拟阵。然后据说就可以得出一个性质：新加入的任务最多只会替换原来的一个任务。。删除同理，就是这个结论的逆，也就是删除一个任务最多只会加入一个任务到答案中。不管这些东西怎么来之后就是很裸的线段树了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
#define N 300050
#define INF 0x3f7f7f7f
#define fr first
#define sc second
#define ll long long
ll ans;char ch[4];bool b[N];int st,n,m,v[N][2],ne[N];
map <pair <int,int>,int> Ha;
multiset <pair <int,int> > s[N][2];
set <pair <int,int> > :: iterator it;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
struct Segment_Tree
{
int mi[N*4],ad[N*4];pair <int,int> ma[N*4];
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
mi[z]=x;ma[z]=make_pair(-INF,0);
if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
}
inline void adj(int x,int y,int z)
{
int j=z << 1;
if (!ad[z]) return;
if (x!=y) ad[j]+=ad[z],ad[j+1]+=ad[z];
mi[z]+=ad[z];ad[z]=0;
}
inline pair <int,int> Getmax(pair <int,int> x,pair <int,int> y,bool flag)
{return flag?(x.fr<y.fr?y:x):(y.fr<x.fr?x:y);}
inline void Update(int x,int y,int z,bool flag)
{
int j=z << 1;
if (x==y)
{
it=s[x][flag].end();
if (it!=s[x][flag].begin())
ma[z]=*(--it); else
ma[z]=make_pair(-INF,0);
return;
}
mi[z]=min(mi[j],mi[j+1]);ma[z]=Getmax(ma[j],ma[j+1],flag);
}
inline pair <int,int> Trans(int y,bool flag)
{return make_pair(flag?-v[y][1]:v[y][1],y);}
void Delete(int x,int y,int z,int o,int p,bool flag)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y)
{
if (flag) ad[z]=1;
s[x][flag].erase(Trans(p,flag));
adj(x,y,z);Update(x,y,z,flag);return;
}
if (o>i) Delete(i+1,y,j+1,o,p,flag),adj(x,i,j); else
Delete(x,i,j,o,p,flag),
ad[j+1]+=flag?1:0,adj(i+1,y,j+1);
Update(x,y,z,flag);
return;
}
void Insert(int x,int y,int z,int o,int p,bool flag)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y)
{
if (flag) ad[z]=-1;
s[x][flag].insert(Trans(p,flag));
adj(x,y,z);Update(x,y,z,flag);return;
}
if (o>i) Insert(i+1,y,j+1,o,p,flag),adj(x,i,j); else
Insert(x,i,j,o,p,flag),
ad[j+1]+=flag?-1:0,adj(i+1,y,j+1);
Update(x,y,z,flag);
return;
}
pair <int,int> Query(int x,int y,int z,int o,int p,bool flag)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) return ma[z];
if (p<=i) return Query(x,i,j,o,p,flag); else
if (o>i) return Query(i+1,y,j+1,o,p,flag); else
return Getmax(Query(x,i,j,o,i,flag),Query(i+1,y,j+1,i+1,p,flag),flag);
}
int Find_Left(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1,k=0;adj(x,y,z);
if (x==y) return !mi[z]?x:0; else
adj(x,i,j),adj(i+1,y,j+1);
if (!mi[j]&&o<=i) k=Find_Left(x,i,j,o);
if (!k&&!mi[j+1]) k=Find_Left(i+1,y,j+1,max(o,i+1));
return k;
}
int Find_Right(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y) return !mi[z]?x:0; else
adj(x,i,j),adj(i+1,y,j+1);
if (!mi[j+1]) return Find_Right(i+1,y,j+1); else
return Find_Right(x,i,j);
}
} A,B;
void Delete(int x,int y)
{
int sg=Ha[make_pair(x,y)];
Ha[make_pair(x,y)]=ne[sg];
if (!b[sg]) {B.Delete(1,n,1,x,sg,false);return;}
A.Delete(1,n,1,x,sg,true);int k=A.Find_Right(1,n,1);
k=B.Query(1,n,1,k+1,n,false).sc;ans-=y;b[sg]=false;
if (k)
B.Delete(1,n,1,v[k][0],k,false),
A.Insert(1,n,1,v[k][0],k,true),
ans+=v[k][1],b[k]=true;
return;
}
void Insert(int x,int y)
{
v[++st][0]=x;v[st][1]=y;
ne[st]=Ha[make_pair(x,y)];Ha[make_pair(x,y)]=st;
int k=A.Find_Left(1,n,1,x);
if (!k&&y>=0)
{A.Insert(1,n,1,x,st,true);b[st]=true;ans+=y;return;}
k=A.Query(1,n,1,1,k,true).sc;
if (v[k][1]>=y) B.Insert(1,n,1,x,st,false); else
{
A.Delete(1,n,1,v[k][0],k,true);b[k]=false;
B.Insert(1,n,1,v[k][0],k,false);
A.Insert(1,n,1,x,st,true);b[st]=true;
ans+=y-v[k][1];
}
return;
}
int main()
{
n=Read();m=Read();A.Set_up(1,n,1);B.Set_up(1,n,1);
for (int i=1;i<=m;i++)
{
int k,l;scanf("%s%d%d",ch,&k,&l);
if (ch[0]=='D') Delete(k,l); else Insert(k,l);
printf("%lld\n",ans);
}
return 0;
}
BZOJ3435 [WC2014]紫荆花之恋：经典题，替罪羊树套点分治套treap。因为替罪羊维持平衡的部分出了些微妙的错误导致TLE一直都没看出来= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;
#define N 100050
#define M 6000050
#define P 4000050
#define INF (int)1e9
#define eps 0.78
#define ll long long
int c[N*2][3],h[N],dep[N],r[N],li[N],n,m,ss=1;
ll ans;int dis[N][30],fi[N],Dis[N];bool Flag;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;c[ss][2]=z;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;c[ss][2]=z;
}
struct Node
{
Node *c[2];int v,s,val;
} used[P],*unused[P],*pool = used,**top = unused,*rt[N][2],Emp,*emp=&Emp;
struct Balance_Tree
{
inline Node* Get(int x)
{
Node *k = (top != unused) ? *--top : pool++;
k->c[0]=k->c[1]=emp;
k->s=1;k->v=x;k->val=rand();
return k;
}
inline void Update(Node *x)
{x->s=x->c[0]->s+x->c[1]->s+1;}
void Rotate(Node* &x,Node* y)
{
bool k=y==x->c[0];
x->c[!k]=y->c[k];y->c[k]=x;
y->s=x->s;Update(x);x=y;
return;
}
void Insert(Node* &x,Node* y)
{
bool flag=y->v>x->v;
if (x==emp) {x=y;return;} else x->s++;
Insert(x->c[flag],y);
if (x->c[flag]->val>x->val)
Rotate(x,x->c[flag]);
return;
}
int Query(Node* x,int y)
{
if (x==emp) return 0;
if (y>=x->v) return x->c[0]->s+1+Query(x->c[1],y); else
return Query(x->c[0],y);
}
void Clear(Node* &x)
{
if (x==emp) return;
*top++ = x;
Clear(x->c[0]);Clear(x->c[1]);
x=emp;
}
Node* Rebuild(int x,int y)
{
Node* Rt=Get(dis[li[1]][y]-r[li[1]]);
for (int i=2;i<=x;i++)
Insert(Rt,Get(dis[li[i]][y]-r[li[i]]));
return Rt;
}
} B;
struct Divide_Tree
{
int suf[N],cnt[N],sg[N],sz[N],Rt,Sg;
int Get_Size(int x)
{
int le=1,ri=1;li[1]=x;sz[x]=-1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!sz[c[i][0]]&&!sg[c[i][0]])
sz[li[++ri]=c[i][0]]=-1;
return ri;
}
int Get_Rt(int Cnt)
{
int Ctr=li[1];
for (int i=Cnt;i>=1;i--)
{
sz[li[i]]=1;
for (int j=fi[li[i]];j;j=c[j][1])
if (!sg[c[j][0]]&&sz[c[j][0]]>0) sz[li[i]]+=sz[c[j][0]];
}
while (true)
{
bool flag=false;
for (int i=fi[Ctr];i;i=c[i][1])
if (sz[c[i][0]]<sz[Ctr]&&!sg[c[i][0]]&&sz[c[i][0]]*2>=Cnt)
{Ctr=c[i][0];flag=true;break;}
if (!flag) break;
}
for (int i=1;i<=Cnt;i++) sz[li[i]]=0;
return Ctr;
}
void DFS(int x,int y,int z)
{
for (int i=fi[x];i;i=c[i][1])
if (!sg[c[i][0]]&&c[i][0]!=y)
dis[c[i][0]][z]=dis[x][z]+c[i][2],
DFS(c[i][0],x,z);
return;
}
void Rebuild(int x,int y,int z)
{
int Cnt=Get_Size(x),Ctr=Get_Rt(Cnt);
dis[Ctr][y]=0;DFS(Ctr,0,y);sg[Ctr]=y;
if (z) suf[Ctr]=z; else
suf[Rt=Ctr]=0,rt[Ctr][1]=emp;
rt[Ctr][0]=B.Rebuild(Cnt,y);cnt[Ctr]=Cnt;
if (y>1) rt[Ctr][1]=B.Rebuild(Cnt,y-1);
for (int i=fi[Ctr];i;i=c[i][1])
if (!sg[c[i][0]]) Rebuild(c[i][0],y+1,Ctr);
return;
}
void Clear(int x)
{
if (!sg[x]||sg[x]<Sg) return;sg[x]=0;
B.Clear(rt[x][0]);B.Clear(rt[x][1]);
for (int i=fi[x];i;i=c[i][1]) Clear(c[i][0]);
}
void Get(int x,int y)
{
cnt[x]=1;sg[x]=sg[suf[x]]+1;int ma=0;
rt[x][0]=B.Get(-y);rt[x][1]=B.Get(c[ss][2]-y);
memcpy(dis[x],dis[suf[x]],sizeof dis[suf[x]]);
for (int i=1;i<sg[x];i++) dis[x][i]+=c[ss][2];
dis[x][sg[x]]=0;
for (int i=suf[x],j=sg[x]-1;i;i=suf[i],j--)
{
cnt[i]++;
if (j-1&&cnt[i]/(cnt[suf[i]]+1.0)>eps) ma=suf[i];
ans+=B.Query(rt[i][0],y-dis[x][j]);
B.Insert(rt[i][0],B.Get(dis[x][j]-y));
if (j-1)
ans-=B.Query(rt[i][1],y-dis[x][j-1]),
B.Insert(rt[i][1],B.Get(dis[x][j-1]-y));
}
if (ma)
Sg=sg[ma],Clear(ma),Rebuild(ma,Sg,suf[ma]);
return;
}
} A;
int main()
{
Read();n=Read();Read();Read();
A.Rt=1;Emp.c[0]=Emp.c[1]=&Emp;
srand(23335900);//Orz TATQAQ2333 and yyh5900
A.Get(1,r[1]=Read());puts("0");
for (int i=2;i<=n;i++)
{
int q=Read()^(ans%INF),w=Read();r[i]=Read();
h[i]=h[q]+1;dep[i]=dep[q]+w;
Line(i,q,w);A.suf[i]=q;
A.Get(i,r[i]);printf("%lld\n",ans);
}
return 0;
}
BZOJ3068 小白树：直接枚举断边就好。然后答案就是分成的两棵树的重心。至于为什么因为每种方案都对应了至少一个断边，然而每种断边的最优解又肯定是在两棵树重心处。所以虽然不一定一个两棵树的重心的断边一定是枚举的那个但是这种方案肯定是比其它断边为这条的方案更优的。所以就只要求出一个东西：一棵子树的重心和对应答案是什么。去掉这棵子树的重心和对应答案是什么。前面那个东西很好求，只需要求出一个点每棵子树的答案然后再找出自身的重心在哪棵子树，然后暴力往上移动就好。这种方法类似于启发式合并，复杂度也是一样。至于求一棵子树的补的重心，我们考虑二分答案。首先设去掉的子树的父亲是i，那么如果在i的某棵子树内，就肯定是在这棵子树的重心和i的连线上。如果是在i的上面，就肯定在fai的重心和i的连线上。于是二分答案然后通过子树重量判断就好。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500050
#define M 19
#define ll long long
int fa[N][M],h[N],ma[N][2],v[N],fi[N],c[N*2][2],li[N],n,m,ss=1;
ll cnt[N][2],Ans[N][2],Cnt[N],ans,Aha;int la[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void Get()
{
int le=1,ri=1;li[1]=1;h[1]=1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (c[i][0]!=fa[li[le]][0])
fa[c[i][0]][0]=li[le],h[li[++ri]=c[i][0]]=h[li[le]]+1;
return;
}
void DFS()
{
for (int t=n;t>=1;t--) {
int x=li[t];cnt[x][0]=v[x];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
{
cnt[x][0]+=cnt[c[i][0]][0];
cnt[x][1]+=cnt[c[i][0]][0]+cnt[c[i][0]][1];
if (cnt[c[i][0]][0]>=cnt[ma[x][0]][0])
ma[x][1]=ma[x][0],ma[x][0]=c[i][0]; else
if (cnt[c[i][0]][0]>=cnt[ma[x][1]][0])
ma[x][1]=c[i][0];
}
if (ma[x][0]&&cnt[ma[x][0]][0]*2>=cnt[x][0])
{
Ans[x][0]=Ans[ma[x][0]][0];
Ans[x][1]=Ans[ma[x][0]][1]+cnt[x][1]-cnt[ma[x][0]][1]-
cnt[ma[x][0]][0]+(cnt[x][0]-cnt[ma[x][0]][0])*
(h[Ans[x][0]]-h[x]);
while (cnt[Ans[x][0]][0]*2<cnt[x][0])
Ans[x][1]+=2*cnt[Ans[x][0]][0]-cnt[x][0],
Ans[x][0]=fa[Ans[x][0]][0];
} else Ans[x][0]=x,Ans[x][1]=cnt[x][1];
}
return;
}
inline ll min(ll x,ll y)
{return x<y?x:y;}
void DSF()
{
for (int t=1;t<=n;t++) {
int x=li[t];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
Cnt[c[i][0]]=Cnt[x]-2*cnt[c[i][0]][0]+Aha;
}
return;
}
int LCA(int x,int y)
{
if (h[x]<h[y]) swap(x,y);
for (int i=M-1;i>=0;i--)
if (h[fa[x][i]]>=h[y]) x=fa[x][i];
if (x!=y)
{
for (int i=M-1;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
x=fa[x][0];
}
return x;
}
int Up(int x,int y,ll z,ll o)
{
if (x!=y&&(cnt[x][0]+o)*2>=z) return x;
for (int i=M-1;i>=0;i--)
if (fa[x][i]&&(cnt[fa[x][i]][0]+o)*2<z) x=fa[x][i];
return h[x]-1>h[y]?fa[x][0]:0;
}
void DFF()
{
for (int t=1;t<=n;t++) {
int x=li[t],y=la[x];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
{
ll k=Aha-cnt[c[i][0]][0],l=0,Tot=0;int e=0;
if ((Aha-cnt[x][0])*2>=k) l=-1; else
if (cnt[ma[x][0]][0]*2>=k&&ma[x][0]!=c[i][0])
l=ma[x][0]; else
if (ma[x][1]&&cnt[ma[x][1]][0]*2>=k&&
ma[x][1]!=c[i][0]) l=ma[x][1];
if (!l)
e=x,Tot=Cnt[x]-cnt[c[i][0]][1]-cnt[c[i][0]][0]; else
if (l>0)
e=Up(Ans[l][0],x,k,0),
Tot=Cnt[e]-cnt[c[i][0]][1]-
cnt[c[i][0]][0]*(1+h[e]-h[x]); else
{
l=LCA(y,x);ll tot=0;e=Up(y,l,k,0);
if (!e)
e=Up(x,fa[l][0],k,-cnt[c[i][0]][0]),
Tot=Cnt[e]-cnt[c[i][0]][1]-cnt[c[i][0]][0]*
(h[c[i][0]]-h[e]); else
Tot=Cnt[e]-cnt[c[i][0]][1]-cnt[c[i][0]][0]*
(h[e]+h[c[i][0]]-2*h[l]);
}
ans=min(ans,Tot+Ans[c[i][0]][1]);
la[c[i][0]]=e;
}
}
return;
}
void Solve()
{
Get();DFS();
for (int i=1;i<M;i++)
for (int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
Cnt[1]=cnt[1][1];DSF();DFF();
return;
}
int main()
{
n=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
for (int i=1;i<=n;i++) Aha+=(v[i]=Read());
ans=1LL << 60;Solve();
cout <<ans<<endl;
return 0;
}
HDU5574 [ACM 2015 Shanghai]：Colorful Tree
DFS序建线段树，两棵线段树分别维护答案和标记个数。设一个点的颜色为它上面第一个标记的颜色。每次相当于添加一个标记以及将子树内所有标记删除。于是考虑删除一个标记对答案的影响：如果子树内还有同色标记无影响，否则其直到与其DFS序相邻的两个标记的最深LCA的路径上面的答案-1，这东西树剖维护即可。添加标记同理，只不过子树内所有点答案赋为1。复杂度两个log。课件上面这么写的。。后来写了之后才发现只考虑最近的两个标记是有问题的。如果一个点祖先也有同色标记，那么标记下面到修改点的路径上面就会答案加一。但其实是最深同色点到修改点的路径上面答案加一。同时还要考虑DFS序相邻的两个点。所以应该修改的路径应该是原来求的东西和最深祖先同色点中的最深点，这东西用set维护一下就好。这部分复杂度也是两个log。我的写法应该是最丑的吧。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
int rf[N],c[N*2][2],fa[N],fi[N],mark[N],li[N],sg[N][2],h[N];
int ms[N*4],cs[N*4],ad[N*4],s[N],v[N],n,m,ss,st,t;bool xg[N*4];
multiset <int> ne[N],Mark;bool Flag;
set <int> :: iterator it;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x]=h[fa[x]]+1;s[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),s[x]+=s[c[i][0]];
return;
}
void DSF(int x,int y)
{
rf[x]=y;int k=0;li[sg[x][0]=++st]=x;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&s[c[i][0]]>s[k]) k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k) DSF(c[i][0],c[i][0]);
sg[x][1]=st;
return;
}
inline void xgj(int x,int y,int z)
{
int j=z << 1;
if (!xg[z]) return;
if (x!=y)
for (int i=0;i<2;i++)
ad[j+i]=false,xg[j+i]=true; else cs[z]=1;
xg[z]=false;return;
}
inline void adj(int x,int y,int z)
{
int j=z << 1;
if (!ad[z]) return;
if (x!=y)
ad[j]+=ad[z],ad[j+1]+=ad[z]; else cs[z]+=ad[z];
ad[z]=0;return;
}
int Query(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;
xgj(x,y,z);adj(x,y,z);
if (x==y) return cs[z];
if (o<=i) return Query(x,i,j,o); else
return Query(i+1,y,j+1,o);
}
void Insert(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;ms[z]++;
if (x==y) return;
if (o<=i) Insert(x,i,j,o); else Insert(i+1,y,j+1,o);
return;
}
void Add(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=z << 1;
xgj(x,y,z);adj(x,y,z);
if (x==o&&y==p) {ad[z]=u;adj(x,y,z);return;}
if (p<=i) Add(x,i,j,o,p,u); else
if (o>i) Add(i+1,y,j+1,o,p,u); else
Add(x,i,j,o,i,u),Add(i+1,y,j+1,i+1,p,u);
return;
}
void Modify(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
xgj(x,y,z);adj(x,y,z);
if (x==o&&y==p) {xg[z]=true;xgj(x,y,z);return;}
if (p<=i) Modify(x,i,j,o,p); else
if (o>i) Modify(i+1,y,j+1,o,p); else
Modify(x,i,j,o,i),Modify(i+1,y,j+1,i+1,p);
return;
}
void Increase(int x,int y,int z)
{
while (rf[x]!=rf[y])
Add(1,n,1,sg[rf[x]][0],sg[x][0],z),x=fa[rf[x]];
Add(1,n,1,sg[y][0],sg[x][0],z);
return;
}
int LCA(int x,int y)
{
int lx=0;
while (rf[x]!=rf[y])
{
bool flag=false;
if (h[rf[y]]>h[rf[x]]) swap(x,y),flag=true;
x=rf[x];if (!flag) lx=x;x=fa[x];
if (flag) swap(x,y);
}
if (h[x]<=h[y]) return lx; else return li[sg[y][0]+1];
}
inline int Lower(int x,int y)
{return x==-1||h[x]<h[y]?y:x;}
int Get(int x,int y)
{
int k=-1,l=x,e;
while (l)
{
it=ne[y].lower_bound(sg[l][0]+1);
if (it!=ne[y].begin())
if (*(--it)!=sg[x][0]) it++;
if (it!=ne[y].begin()&&(*(--it)>=sg[rf[l]][0]))
{k=li[*it];break;}
l=fa[rf[l]];
}
if (k==-1) return k;l=e=x;
while (l)
{
it=Mark.lower_bound(rf[l]==rf[k]?sg[k][0]+1:sg[rf[l]][0]);
if (it!=Mark.end()&&*it<=sg[l][0]) e=li[*it];
if (rf[l]==rf[k]) break;
l=fa[rf[l]];
}
return e;
}
void Pop(int x,int y)
{
if (!mark[x]) return;
Mark.erase(sg[x][0]);int k=Get(x,y);
it=ne[y].lower_bound(sg[x][0]);
if (it!=ne[y].begin()) k=Lower(k,LCA(x,li[*(--it)])),it++;
if (++it!=ne[y].end())
{
int l=*it;
if (sg[li[l]][1]<=sg[x][1]) {it--;ne[y].erase(it);return;}
k=Lower(k,LCA(x,li[l]));
}
it--;ne[y].erase(it);
Increase(x,k==-1?1:k,-1);
return;
}
void Push(int x,int y)
{
Insert(1,n,1,sg[x][0]);ne[y].insert(sg[x][0]);
int k=Get(x,y);Mark.insert(sg[x][0]);
it=ne[y].lower_bound(sg[x][0]);
if (it!=ne[y].begin()) k=Lower(k,LCA(x,li[*(--it)])),it++;
if (++it!=ne[y].end())
{
int l=*it;
if (sg[li[l]][1]<=sg[x][1]) return;
k=Lower(k,LCA(x,li[l]));
}
Increase(x,k==-1?1:k,1);
return;
}
void Delete(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (!ms[z]) return;
if (x==y) {Pop(li[x],mark[li[x]]);mark[li[x]]=ms[z]=0;return;}
if (p<=i) Delete(x,i,j,o,p); else
if (o>i) Delete(i+1,y,j+1,o,p); else
Delete(x,i,j,o,i),Delete(i+1,y,j+1,i+1,p);
ms[z]=ms[j]+ms[j+1];
return;
}
void Gay_a_wave(int y,int x)
{
Delete(1,n,1,sg[x][0],sg[x][1]);
Push(x,y);mark[x]=y;Modify(1,n,1,sg[x][0],sg[x][1]);
}
void Pretreat()
{
DFS(1);DSF(1,1);
for (int i=1;i<=n;i++) Gay_a_wave(v[li[i]],li[i]);
return;
}
void Clear(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
cs[z]=ms[z]=xg[z]=ad[z]=false;
if (x!=y) Clear(x,i,j),Clear(i+1,y,j+1);
}
int main()
{
t=Read();
for (int T=1;T<=t;T++)
{
printf("Case #%d:\n",T);
n=Read();ss=1;st=0;
for (int i=1;i<n;i++) Line(Read(),Read());
for (int i=1;i<=n;i++) v[i]=Read();
Pretreat();m=Read();Flag=true;
for (int i=1;i<=m;i++)
if (Read())
printf("%d\n",Query(1,n,1,sg[Read()][0])); else
Gay_a_wave(Read(),Read());
for (int i=1;i<=n;i++)
fi[i]=mark[i]=false,ne[i].clear();
Mark.clear();Clear(1,n,1);
}
return 0;
}
评论 (0)
