SPOJ 10707 Count on a tree II_综合

SPOJ 10707 Count on a tree II

题意：
给定 $n$ 个结点的树，每个结点有一种颜色。
$m$ 次询问，每次询问给出 $u$ ， $v$ 回答 $u$ ， $v$ 之间的路径上的结点的不同颜色数。
$n < = 4 e 4$ ， $m < = 1 e 5$ ，颜色是不超过 $2 e 9$ 的非负整数。

思路一：
因为是允许离线的，我们考虑暴力——树上莫队。
利用树上欧拉序的特点，我们可以用莫队来跑欧拉序，和普通莫队相似。
但是需要特判 $l c a$ ，我们在一次遍历的时候，求出欧拉序，再遍历一次，进行树剖即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long longint n,m,M;
int col[40004],c[40005];
int len;
int cnt[40005];
int res=0;
vector<int>v[40005];
int siz[40005],son[40006],top[40006],dep[40006],fa[40005];
int st[40006],ed[40005],ans[100005];
int s[100050];
struct node{
    int l,r,id;int lc;
}z[100006];
int tot=0;void dfs1(int x,int pre){
    s[++tot]=x;st[x]=tot;fa[x]=pre;dep[x]=dep[pre]+1;siz[x]=1;for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre)continue;dfs1(to,x);siz[x]+=siz[to];if(siz[to]>siz[son[x]])son[x]=to;}s[++tot]=x;ed[x]=tot;
}
void dfs2(int x,int pre){
    if(son[pre]==x)top[x]=top[pre];else top[x]=x;if(son[x])dfs2(son[x],x);for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre||to==son[x])continue;dfs2(to,x);}
}
int lca(int x,int y){
    while(top[x]!=top[y]){
    if(dep[top[x]]>dep[top[y]])swap(x,y);y=fa[top[y]];}if(dep[x]>dep[y])swap(x,y);return x;
}
int vis[100005];
bool cmp(node a,node b){
    if(a.l/M!=b.l/M)return a.l<b.l;else return a.r<b.r;
}
void add(int x){
    if(vis[x]==0){
    if(cnt[col[x]]==0)res++;cnt[col[x]]++;vis[x]=1;}else{
    if(cnt[col[x]]==1)res--;cnt[col[x]]--;vis[x]=0;}
}
int main(){
    scanf("%d%d",&n,&m);M=sqrt(2*n);for(int i=1;i<=n;i++){
    scanf("%d",&col[i]);c[i]=col[i];}sort(c+1,c+1+n);len=unique(c+1,c+1+n)-c-1;for(int i=1;i<=n;i++){
    col[i]=lower_bound(c+1,c+1+len,col[i])-c;}for(int i=1;i<n;i++){
    int a,b;scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}dfs1(1,0);dfs2(1,0);for(int i=1;i<=m;i++){
    int a,b;scanf("%d%d",&a,&b);if(st[a]>st[b])swap(a,b);if(a!=lca(a,b))z[i].lc=lca(a,b),z[i].l=ed[a];else z[i].l=st[a];z[i].r=st[b];z[i].id=i;}sort(z+1,z+1+m,cmp);int l=1,r=0;for(int i=1;i<=m;i++){
    while(l>z[i].l){
    l--;add(s[l]);}while(r<z[i].r){
    r++;add(s[r]);}while(l<z[i].l){
    add(s[l]);l++;}while(r>z[i].r){
    add(s[r]);r--;}if(z[i].lc)add(z[i].lc);ans[z[i].id]=res;if(z[i].lc)add(z[i].lc);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}

思路二：
如果离线，就是莫队裸题啦，但如果是在线呢；
考虑树上分块，（采用王室联邦分块，保证块的大小、块的直径、块的个数，不保证连通性）
对于块内的答案，我们可以暴力跑出答案；
对于不同块的询问，我们可以预处理出，块顶到块顶的 bitset，然后再直接跳块就好了；

亲身证明，好像王室联邦因为常数等原因，就是会T；
所以我们，考虑另一种分块，按照深度分块，这样保证每个点向上跳的次数是在我们设的阈值范围内的。
然后，一条从 $a$ 到 $b$ 的路径，就变成了 $a$ 到 $l c a$ ，以及 $b$ 到 $l c a$ 的路径。
两者相似，我们只讨论从 $a$ 到 $l c a$ ，先把 $a$ 跳到块顶，然后跳块到 $l c a$ 的块，然后再在块中暴力。
代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long longinline int qread(){
    int s=0,w=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);return (w==-1?-s:s);}bitset<40002>bt[102][102],nw;
vector<int>vec;
int n,m,col[40002],fa[40002],dep[40002],mxd[40002],ff[40002],siz[40002];
int tp[40002],son[40002],id[40002],st[40002],gg[40002];
//ff数组 块顶的父亲（上一个块顶），gg记录块树上当前块的深度 
vector<int>v[40002];
int tot=0,ans=0,top=0;void dfs(int x,int pre){
    siz[x]=1;dep[x]=dep[pre]+1;fa[x]=pre;mxd[x]=dep[x];for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre)continue;dfs(to,x);siz[x]+=siz[to];if(mxd[to]>mxd[x])mxd[x]=mxd[to];if(siz[to]>siz[son[x]])son[x]=to;}if(mxd[x]-dep[x]>=400)id[x]=++tot,mxd[x]=dep[x];
}void dfs2(int x,int pre){
    for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre)continue;if(id[to]){
    int ip=id[st[top]],in=id[to];for(int p=to;p!=st[top];p=fa[p])bt[ip][in].set(col[p]);nw=bt[ip][in];for(int j=1;j<top;j++){
    bitset<40002>&bs=bt[id[st[j]]][in];bs=bt[id[st[j]]][ip];bs|=nw;}ff[to]=st[top],gg[to]=gg[st[top]]+1;st[++top]=to;}dfs2(to,x);if(id[to])--top;}
}
void dfs3(int x,int pre){
    if(son[pre]==x)tp[x]=tp[pre];else tp[x]=x;if(son[x])dfs3(son[x],x);for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre||to==son[x])continue;dfs3(to,x);}
}
int lca(int x,int y){
    while(tp[x]!=tp[y]){
    if(dep[tp[x]]>dep[tp[y]])swap(x,y);y=fa[tp[y]];}if(dep[x]>dep[y])swap(x,y);return x;
}
int main(){
    n=qread();m=qread();for(int i=1;i<=n;i++){
    col[i]=qread();vec.push_back(col[i]);}sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());for(int i=1;i<=n;i++){
    col[i]=lower_bound(vec.begin(),vec.end(),col[i])-vec.begin();}for(int i=1;i<n;i++){
    int a,b;a=qread();b=qread();v[a].push_back(b);v[b].push_back(a);}dfs(1,0);if(!id[1])id[1]=++tot;top=1;st[1]=gg[1]=1;dfs2(1,0);dfs3(1,0);while(m--){
    int a,b;a=qread(),b=qread();nw.reset();int lc=lca(a,b);while(a!=lc&&!id[a])nw.set(col[a]),a=fa[a];while(b!=lc&&!id[b])nw.set(col[b]),b=fa[b];if(a!=lc){
    int pr=a;while(dep[ff[pr]]>=dep[lc])pr=ff[pr];if(pr!=a)nw|=bt[id[pr]][id[a]];while(pr!=lc)nw.set(col[pr]),pr=fa[pr];}if(b!=lc){
    int pr=b;while(dep[ff[pr]]>=dep[lc])pr=ff[pr];if(pr!=b)nw|=bt[id[pr]][id[b]];while(pr!=lc)nw.set(col[pr]),pr=fa[pr];}nw.set(col[lc]);printf("%d\n",ans=nw.count());}return 0;
}

P6177 Count on a tree II

这道题时间多，空间小，调整一下块的大小即可。
别忘了吸氧~

#include<bits/stdc++.h>
using namespace std;
#define ll long longinline int qread(){
    int s=0,w=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);return (w==-1?-s:s);}bitset<40002>bt[42][42],nw;
vector<int>vec;
int n,m,col[40002],fa[40002],dep[40002],mxd[40002],ff[40002],siz[40002];
int tp[40002],son[40002],id[40002],st[40002],gg[40002];
//ff数组 块顶的父亲（上一个块顶），gg记录块树上当前块的深度 
vector<int>v[40002];
int tot=0,ans=0,top=0;void dfs(int x,int pre){
    siz[x]=1;dep[x]=dep[pre]+1;fa[x]=pre;mxd[x]=dep[x];for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre)continue;dfs(to,x);siz[x]+=siz[to];if(mxd[to]>mxd[x])mxd[x]=mxd[to];if(siz[to]>siz[son[x]])son[x]=to;}if(mxd[x]-dep[x]>=1000)id[x]=++tot,mxd[x]=dep[x];
}void dfs2(int x,int pre){
    for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre)continue;if(id[to]){
    int ip=id[st[top]],in=id[to];for(int p=to;p!=st[top];p=fa[p])bt[ip][in].set(col[p]);nw=bt[ip][in];for(int j=1;j<top;j++){
    bitset<40002>&bs=bt[id[st[j]]][in];bs=bt[id[st[j]]][ip];bs|=nw;}ff[to]=st[top],gg[to]=gg[st[top]]+1;st[++top]=to;}dfs2(to,x);if(id[to])--top;}
}
void dfs3(int x,int pre){
    if(son[pre]==x)tp[x]=tp[pre];else tp[x]=x;if(son[x])dfs3(son[x],x);for(int i=0;i<v[x].size();i++){
    int to=v[x][i];if(to==pre||to==son[x])continue;dfs3(to,x);}
}
int lca(int x,int y){
    while(tp[x]!=tp[y]){
    if(dep[tp[x]]>dep[tp[y]])swap(x,y);y=fa[tp[y]];}if(dep[x]>dep[y])swap(x,y);return x;
}
int main(){
    n=qread();m=qread();for(int i=1;i<=n;i++){
    col[i]=qread();vec.push_back(col[i]);}sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());for(int i=1;i<=n;i++){
    col[i]=lower_bound(vec.begin(),vec.end(),col[i])-vec.begin();}for(int i=1;i<n;i++){
    int a,b;a=qread();b=qread();v[a].push_back(b);v[b].push_back(a);}dfs(1,0);if(!id[1])id[1]=++tot;top=1;st[1]=gg[1]=1;dfs2(1,0);dfs3(1,0);while(m--){
    int a,b;a=qread(),b=qread();nw.reset();a=a^ans;int lc=lca(a,b);while(a!=lc&&!id[a])nw.set(col[a]),a=fa[a];while(b!=lc&&!id[b])nw.set(col[b]),b=fa[b];if(a!=lc){
    int pr=a;while(dep[ff[pr]]>=dep[lc])pr=ff[pr];if(pr!=a)nw|=bt[id[pr]][id[a]];while(pr!=lc)nw.set(col[pr]),pr=fa[pr];}if(b!=lc){
    int pr=b;while(dep[ff[pr]]>=dep[lc])pr=ff[pr];if(pr!=b)nw|=bt[id[pr]][id[b]];while(pr!=lc)nw.set(col[pr]),pr=fa[pr];}nw.set(col[lc]);printf("%d\n",ans=nw.count());}return 0;
}