link
很简单一道题，考场上脑残了。
很容易想到离线处理，又很容易想到可以拆分询问（树上路径询问要么用树链剖分拆成若干小段，要么用树上前缀拆成三段加减），又很容易想到可以用map和O2解决问题。
艹，考场上想的八九不离十了，结果脑子一抽用莫队加Trie来写，喜提0分。悲哀。
STL大法好啊！
#include #include #include #include #include #define zczc using namespace std; const int N=100010; const int S=12; inline void read(int &wh){ wh=0;int f=1;char w=getchar(); while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();} while(w>='0'&&w<='9'){wh=wh*10+w-'0';w=getchar();} wh*=f;return; } inline void swap(int &s1,int &s2){ int s3=s1;s1=s2;s2=s3;return; } struct vv{int a[S],len;}; int m,n; struct edge{int t,next;string v;}e[N<<1]; int head[N],esum; void add(int fr,int to,string val){ e[++esum]=(edge){to,head[fr],val};head[fr]=esum; } int tot,dfn[N],d[N],nxt[N][22]; void dfs(int wh,int fa,int deep){ dfn[wh]=++tot;nxt[wh][0]=fa;d[wh]=deep+1; for(int i=1;i<=20;i++)nxt[wh][i]=nxt[nxt[wh][i-1]][i-1]; for(int i=head[wh],th;i;i=e[i].next) if((th=e[i].t)^fa)dfs(th,wh,deep+1); } int lca(int s1,int s2){ if(d[s1]=0;i--) if(d[nxt[s1][i]]>=d[s2])s1=nxt[s1][i]; if(s1==s2)return s1; for(int i=20;i>=0;i--) if(nxt[s1][i]^nxt[s2][i])s1=nxt[s1][i],s2=nxt[s2][i]; return nxt[s1][0]; } struct node{ int id,op,pl;string val; }c[N<<2];int sr; inline bool cmp(node s1,node s2){ return dfn[s1.pl]mp; void solve(int wh,int fa){ while(use<=sr&&dfn[c[use].pl]<=dfn[wh]){ ans[c[use].id]+=c[use].op*mp[c[use].val]; use++; } for(int i=head[wh],th;i;i=e[i].next){ if((th=e[i].t)==fa)continue; for(int j=0;j<=e[i].v.size();j++)mp[e[i].v.substr(0,j)]++; solve(th,wh); for(int j=0;j<=e[i].v.size();j++)mp[e[i].v.substr(0,j)]--; } } string val; signed main(){ #ifdef zczc freopen("in.txt","r",stdin); #endif int s1,s2;read(m); for(int i=1;i>val;add(s1,s2,val);add(s2,s1,val); } dfs(1,0,1);read(n); for(int i=1;i<=n;i++){ read(s1);read(s2);cin>>val; c[++sr]=(node){i,1,s1,val}; c[++sr]=(node){i,1,s2,val}; c[++sr]=(node){i,-2,lca(s1,s2),val}; } sort(c+1,c+sr+1,cmp); solve(1,0); for(int i=1;i<=n;i++)printf("%d\n",ans[i]); return 0; }