我写一下我考场上的做法吧，也算是退役前留下的最后一点点东西了。
听说D2T1有(O(n))做法，orz
D1T3
首先容易发现，对于一张图(G)，对(f(u,G))有贡献的({v})，是存在一条从(u)到(v)的路径上的点均不小于(v)，且存在一条从(v)到(u)的路径上的点均不小于(v)。
以上对应于原图与反图，保留不小于(v)的点后，(v)均能走到的点数。
总共有(O(m))张图，对于每个(v)，可以(O(m))求一遍，这样暴力的复杂度为(O(m^2n))，我考场上写的这个暴力对拍跑大样例是(0.4ssim 0.5s)的（(n=100,m=1000)），估计能拿(44)分
对于每张图，是没必要都求一遍的：
枚举点(v)，可以动态加入边（从最后一条边加起），当走过一个点后，就把这个点的出边全删掉，记录每个点最早能被(v)遍历到的时间。
这样是(O(nm+n^2))的，具体可以看看我下面的代码
#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
#define opt operator
#define pii std::pair<LL,LL>
const LL maxn=2e5+9,mod=998244353,G=3;
LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
}
return x*f;
}
void Chkmax(LL &x,LL y){
x=y>x?y:x;
}
void Chkmin(LL &x,LL y){
x=y<x?y:x;
}
LL add(LL x,LL y){
x+=y;
return x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
x-=y;
return x<0?x+mod:x;
}
LL mul(LL x,LL y){
return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
LL ret(1);
while(b){
if(b&1) ret=mul(ret,base);
base=mul(base,base); b>>=1;
}
return ret;
}
struct Edge{
LL x,y;
}e[maxn];
LL n,m;
namespace sub2{
LL mark1[maxn],mark2[maxn];
std::vector<LL> V1[maxn],V2[maxn],Q[maxn];
void Bfs1(LL s,LL ti){
std::queue<LL> que; que.push(s);
mark1[s]=ti;
while(que.size()){
LL u(que.front()); que.pop();
for(LL i=0;i<V1[u].size();++i){
LL v(V1[u][i]); if(mark1[v]) continue;
mark1[v]=ti;
que.push(v); //mark1[v]=1;
}
std::vector<LL>().swap(V1[u]);
}
}
void Bfs2(LL s,LL ti){
std::queue<LL> que; que.push(s);
mark2[s]=ti;
while(que.size()){
LL u(que.front()); que.pop();
for(LL i=0;i<V2[u].size();++i){
LL v(V2[u][i]); if(mark2[v]) continue;
mark2[v]=ti;
que.push(v); //mark1[v]=1;
}
std::vector<LL>().swap(V2[u]);
}
}
void Solve(){
static LL cf[maxn];
for(LL i=1;i<=n;++i){
for(LL j=1;j<=n;++j) mark1[j]=mark2[j]=0;
for(LL j=1;j<=n;++j){
std::vector<LL>().swap(V1[j]);
std::vector<LL>().swap(V2[j]);
}
mark1[i]=m+1;
mark2[i]=m+1;
for(LL j=m;j>=1;--j){
LL x(e[j].x),y(e[j].y);
if(x>=i && y>=i){
if(mark1[x] && !mark1[y]){
Bfs1(y,j);
}else if(!mark1[x] && !mark1[y]){
V1[x].pb(y);
}
std::swap(x,y);
if(mark2[x] && !mark2[y]){
Bfs2(y,j);
}else if(!mark2[x] && !mark2[y]){
V2[x].pb(y);
}
}
}
for(LL j=i+1;j<=n;++j) if(mark1[j] && mark2[j]){
LL z(std::min(mark1[j],mark2[j]));
cf[z-1]++;
}
}
for(LL i=m;i>=0;--i) cf[i]+=cf[i+1];
for(LL i=0;i<=m;++i) printf("%d ",cf[i]+n); puts("");
}
}
int main(){
//if(system("diff x.txt "))
//return 0;
// freopen("graph.in","r",stdin);
// freopen("graph.out","w",stdout);
double ret1(clock());
n=Read(); m=Read();
for(LL i=1;i<=m;++i){
LL x(Read()),y(Read());
e[i]=(Edge){x,y};
}
sub2::Solve();
return 0;
//printf("%.10lf
",(clock()-ret1)/CLOCKS_PER_SEC);
}
D2T1
我看了下其他人的代码，说一下，我下面写的特别麻烦，谨慎观看...
这题关键在于，(p_i)均不相同，那么就说明，如果我们知道走到(u)这个位置并且吃掉了，那么现在的状态就已知了。
考虑链的部分分，是可以(O(nlogn))倍增预处理（细节较多不说了）
再考虑树，对树重链剖分，对于(x)往上走到某个祖先节点的贡献，同链
对于(x)往下走到某个子树节点，可以在重链上走，重链上同链那样预处理，总复杂度(O(nlogn+qlog^2n))
#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
#define opt operator
#define pii std::pair<LL,LL>
const LL maxn=2e5+9,mod=998244353,G=3;
LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
}return x*f;
}
LL add(LL x,LL y){
x+=y;
return x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
x-=y;
return x<0?x+mod:x;
}
LL mul(LL x,LL y){
return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
LL ret(1); while(b){
if(b&1) ret=mul(ret,base);
base=mul(base,base); b>>=1;
}return ret;
}
LL m;
LL root[maxn];
namespace Sgt{
LL nod;
LL son[maxn*30][2],a[maxn*30];
void Modify(LL &nw,LL pre,LL l,LL r,LL x,LL v){
nw=++nod;
son[nw][0]=son[pre][0]; son[nw][1]=son[pre][1];
if(l==r){
a[nw]=v; return;
}
LL mid(l+r>>1);
if(x<=mid) Modify(son[nw][0],son[pre][0],l,mid,x,v);
else Modify(son[nw][1],son[pre][1],mid+1,r,x,v);
}
LL Query(LL nw,LL l,LL r,LL x){
if(l==r) return a[nw];
LL mid(l+r>>1);
if(x<=mid) return Query(son[nw][0],l,mid,x);
else return Query(son[nw][1],mid+1,r,x);
}
LL Find(LL u,LL c){
return Query(root[u],1,m,c);
}
}
LL n,C,q;
LL fa[maxn],dep[maxn],p[maxn],w[maxn],pos[maxn],gf[maxn],son[maxn],top[maxn],istop[maxn];
LL size[maxn];
//gf: top first p[1]
LL lp1[maxn][20],lp2[maxn][20],dp1[maxn][20],dp2[maxn][20],inc[maxn][20];
std::vector<LL> V[maxn],col[maxn];
void Init(){
n=Read(); m=Read(); C=Read();
for(LL i=1;i<=C;++i){
p[i]=Read();
}
for(LL i=1;i<=C;++i){
pos[p[i]]=i;
}
for(LL i=1;i<=n;++i) w[i]=Read();
for(LL i=1;i<n;++i){
LL x(Read()),y(Read());
V[x].pb(y); V[y].pb(x);
}
}
void Dfs1(LL u,LL f){
dep[u]=dep[f]+1; fa[u]=f;
LL x(pos[w[u]]);
if(x){
LL y(p[x+1]);
//printf("# %d: %d %d
",u,x,y);
y=(col[y].size()?col[y].back():0);
//printf("%d
",y);
for(LL i=0;i<=19;++i) dp2[u][i]=dp1[y][i];
dp1[u][0]=u;
//dp2[u][0]=y;
for(LL i=1;i<=19;++i){
LL v(dp1[u][i-1]);
dp1[u][i]=dp2[v][i-1];
}
//for(LL i=0;i<=3;++i) printf("%d ",dp1[u][i]); puts("");
//for(LL i=0;i<=3;++i) printf("%d ",dp2[u][i]);
//puts(""); puts("");
}
inc[u][0]=f;
for(LL i=1;i<=19;++i){
inc[u][i]=inc[inc[u][i-1]][i-1];
}
col[w[u]].pb(u);
gf[u]=col[p[1]].size()?col[p[1]].back():0;
size[u]=1; son[u]=0;
for(LL i=0;i<V[u].size();++i){
LL v(V[u][i]); if(v==f) continue;
Dfs1(v,u); size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
col[w[u]].pop_back();
}
void Dfs2(LL u,LL f,LL ff){
istop[son[u]]=0; top[u]=ff;
if(son[u]){
Dfs2(son[u],u,ff);
}
for(LL i=0;i<V[u].size();++i){
LL v(V[u][i]); if(v==f || v==son[u]) continue;
Dfs2(v,u,v);
}
}
void Build2(){//weight lian
Sgt::nod=0;
for(LL i=1;i<=m;++i) std::vector<LL>().swap(col[i]);
std::vector<LL> suq;
for(LL tp=1;tp<=n;++tp) if(istop[tp]){
std::vector<LL> ().swap(suq);
LL u(tp);
while(u){
suq.pb(u); u=son[u];
}
LL sz(suq.size()-1); suq.pb(0);
//for(LL i=sz;i>=0;--i) printf("%d ",suq[i]); puts("");
for(LL i=sz;i>=0;--i){
u=suq[i];
Sgt::Modify(root[suq[i]],root[suq[i+1]],1,m,w[u],u);
}
for(LL i=sz;i>=0;--i){
u=suq[i];
LL x(pos[w[u]]);
if(x){
LL y(p[x+1]);
//printf("# (%d)%d,%d
",u,x,y);
y=(col[y].size()?col[y].back():0);
//printf("%d
",y);
for(LL j=0;j<=19;++j) lp2[u][j]=lp1[y][j];
lp1[u][0]=u;
for(LL j=1;j<=19;++j){
LL v(lp1[u][j-1]);
lp1[u][j]=lp2[v][j-1];
}
//for(LL j=0;j<=3;++j) printf("%d ",lp1[u][j]); puts("");
//for(LL j=0;j<=3;++j) printf("%d ",lp2[u][j]); puts("");
}
col[w[u]].pb(u);
}
for(LL i=0;i<=sz;++i) std::vector<LL>().swap(col[w[suq[i]]]);
}
}
void Build(){
Dfs1(1,0);
//puts("----------------------");
for(LL i=1;i<=n;++i) istop[i]=1;
Dfs2(1,0,1);
Build2();
//puts("-----------------------");
/*for(LL i=1;i<=n;++i){
Dfs3()
}*/
}
LL Lca(LL x,LL y){
if(dep[x]<dep[y]) std::swap(x,y);
for(LL i=19;i>=0;--i) if(dep[inc[x][i]]>=dep[y]) x=inc[x][i];
if(x==y) return x;
for(LL i=19;i>=0;--i) if(inc[x][i]!=inc[y][i]){
x=inc[x][i]; y=inc[y][i];
}return inc[x][0];
}
pii Search1(LL x,LL y){//not in one first:down second:son
while(true){
y=top[y];
if(top[fa[y]]==top[x]) return pii(fa[y],y);
y=fa[y];
}
}
LL Search2(LL x,LL c){//x lian find c
return Sgt::Find(x,c);
}
LL Solve(LL x,LL y){
LL lca(Lca(x,y));
//printf("(%d,%d)%d
",x,y,lca);
LL len(1);
{
LL u(gf[x]);
//printf("# %d
",u);
if(u){
if(dep[u]<dep[lca]){
x=lca;
}else{
x=u;
//for(LL i=0;i<=2;++i) printf("%d ",dp2[x][i]); puts("");
for(LL i=19;i>=0;--i) if(dep[dp2[x][i]]>=dep[lca]){
len+=(1<<i); x=dp2[x][i];
}
++len; x=lca;
}
}else{
x=lca;
}
}
if(len>C) return C;
//printf("%d: %d,%d
",len,x,y);
while(top[x]!=top[y]){
LL z(Search2(x,p[len]));
//puts("#");
pii tmp(Search1(x,y));
//printf("%d (%d,%d)
",z,tmp.first,tmp.second);
if(!z || dep[z]>dep[tmp.first]){
x=tmp.second;
}else{
x=z; //if(len>C) return C;
for(LL i=19;i>=0;--i) if(lp2[x][i] && dep[lp2[x][i]]<=dep[tmp.first]){
len+=(1<<i); x=lp2[x][i];
}
++len; x=tmp.second;
if(len>C) return C;
}
}
if(top[x]==top[y]){
LL z(Search2(x,p[len]));
//printf("# (%d)%d:%d
",x,z,p[len]);
if(!z || dep[z]>dep[y]){
return len-1;
}
x=z;
//printf("# %d
",z);
//for(LL i=0;i<=3;++i) printf("%d ",lp2[x][i]); puts("");
for(LL i=19;i>=0;--i) if(lp2[x][i] && dep[lp2[x][i]]<=dep[y]){
len+=(1<<i); x=lp2[x][i];
}
++len;
assert(len<=C+1);
return len-1;
}
assert(0);
}
void Solve(){
q=Read();
while(q--){
LL x(Read()),y(Read());
LL ret=Solve(x,y);
printf("%d
",ret);
}
}
int main(){
/*
if(system("diff x.txt gem3.ans")) return 0;
else puts("Ac");
return 0;
// */
//freopen("y1.txt","r",stdin);
// freopen("gem.in","r",stdin);
//double ret1(clock());
//freopen("x.txt","w",stdout);
// freopen("gem.out","w",stdout);
Init();
//puts("-----------------");
Build();
//puts("-----------------");
Solve();
//printf("%.10lf
",(clock()-ret1)/CLOCKS_PER_SEC);
return 0;
}