【Codeforces 786D】Rap God
暴力卡常。
题目大意：
给定一棵树，每条边上有一个字母。定义 $\texttt{str(x,y)}$ 表示从 $x$ 到 $y$ 这条路径上经过的所有边依次排列形成的字符串。
多组询问，每次给出 $x,y$，问有多少个 $z$ 满足 $z\neq x,z\neq y$ 且 $\texttt{str(x,y)}$ 的字典序严格大于 $\texttt {str(x,z)}$。
题解：
$n$ 只有 $2\times 10^4$，时限有 $7\texttt s$。
我们考虑 $O(nm)$ 的暴力然后加特技艹过去。
暴力的思路非常简单，每次把这条路径形成的字符串提取出来，然后从 $x$ 开始在树上 dfs。如果遇到一个相同位置字典序小的边，就把它连向的那棵子树的大小加入到答案中。如果遇到一个相同位置且字符相同的边，则递归下去。
直接这么搞，不加任何优化很难通过。
在访问边的时候，要选择友好的方式存储以卡进缓存，否则可能“看起来”可以变快而实际上变慢了。比如我原来开了 $n$ 个 std::vector 存边，后来尝试开了 $26n$ 个结果反而更慢了。
这里使用链表存图是可以通过的。我最终选择的存图方式是先用 std::vector 进行排序，然后把所有边放到一个数组里并保证每个点的连边在数组上是连续的。记录每个点所属的边在数组上的起止位置，访问的时候直接用指针遍历即可。
然后将 dfs 用手工栈转成循环的方式，也可以略微加快速度。
最后还有一个很重要的优化：由于我们存的边的总数是 $2n$，所以每次询问的最坏情况下是遍历 $2n$ 条边。我们将一个点连向父亲的边删掉，每次遍历完所有连边以后再特判父亲的情况。
这看起来变成了访问 $n$ 条边和判断 $n$ 次父亲的情况，没有太大的区别。
事实上它的确有非常明显的效果。
然后基本上就可以通过了。我的代码最慢的点跑了 $6629\texttt{ms}$。
Code：
#include<cstdio>
#include<vector>
#include<algorithm>
const int N=2e4+5;
std::vector<unsigned>G[N];
int n,m,sz[N],son[N],dep[N],fa[N],top[N],ch[N],ans,len,S[N],Top;
unsigned A[N*2],*mem=A,*beg[N],*end[N];
struct node{
int u,p,*s;
}sta[N];
void dfs(int now){
sz[now]=1;
for(unsigned to:G[now])if(!dep[to&65535]){
const int t=to&65535;
dep[t]=dep[now]+1,fa[t]=now,ch[t]=to>>16;
dfs(t);
sz[now]+=sz[t];
if(!son[now]||sz[son[now]]<sz[t])son[now]=t;
}
}
void dfs2(int now){
if(son[now])top[son[now]]=top[now],dfs2(son[now]);
for(unsigned to:G[now]){
const unsigned t=to&65535;
if(dep[t]>dep[now]&&t!=son[now])dfs2(top[t]=t);
}
}
inline int LCA(int x,int y){
while(top[x]!=top[y])if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i){
int u,v;char s[123];
scanf("%d%d%s",&u,&v,s);
G[u].push_back(v|(*s-'a'+1)<<16),G[v].push_back(u|(*s-'a'+1)<<16);
}
dfs(dep[1]=1),dfs2(top[1]=1);
for(int i=1;i<=n;++i){
std::sort(G[i].begin(),G[i].end());
beg[i]=mem;
for(unsigned to:G[i])if((to&65535)!=fa[i])*mem++=to;
end[i]=mem;
}
while(m--){
int u,v;
scanf("%d%d",&u,&v);
int c=LCA(u,v);len=dep[u]+dep[v]-2*dep[c];
int*h=S,*t=S+len;
sta[Top=1]=(node){u,0,S},*t=0,ans=-1;
for(;u!=c;u=fa[u])*h++=ch[u];
for(;v!=c;v=fa[v])*--t=ch[v];
while(Top){
int now=sta[Top].u,pre=sta[Top].p,*s=sta[Top--].s;
++ans;
for(unsigned*it=beg[now],*ed=end[now];it!=ed;++it){
const unsigned t=*it&65535,c=*it>>16;
if(t==pre)continue;
if(c<*s)ans+=sz[t];
else if(c==*s&&s!=S+len-1)sta[++Top]=(node){t,now,s+1};else break;
}
if(now!=1&&pre!=fa[now]){
if(ch[now]<*s)ans+=n-sz[now];
else if(*s==ch[now]&&s!=S+len-1)sta[++Top]=(node){fa[now],now,s+1};
}
}
printf("%d\n",ans);
}
return 0;
}