惯例先看一遍三道题，T1 一开始反应要求割点，但是这是有向图，肯定不能求割点，康了一下数据范围，有40%是树的，还不错，决定待会在打。
看T2 字符串题，完了我字符串最弱了，肯定只能打暴力了，带着前两题都不会的心情，看了T3发现是期望，完了爆0了，在一看，发现是sb原题，还简单一点，赶紧把T3码了一遍过大样例，觉得很稳就交了，然后用一点时间把T1树的分给码了，然后开始磨T2，发现啥都不会开始dfs，一开始觉得只能拿30pts，后来发现没有回溯是$O(n^2)$的，打完就没剩多少时间了，然后考虑T3要不要开long long，觉得没必要就没开石乐智。然后想T1无果。
出分发现T3WA 80，然后把开了long long的代码交上去A了，我怕不是个傻子，不卡时间为什么不开long long啊QAQ。T2A了，T140，后来听说用树的方法跑所有测试点能拿60，艹。少两句话少拿40.jpg。
扯多了2333
T1 attack：
据说是什么支配树裸题，蒟蒻不会，只能照着题解打。
必经关系是一棵树，这好像就是支配树？那么1到k的必经点就是k在这棵树上的祖先，所以我们在有向图中跑个拓扑排序，就可以建出这棵树，但实际上我们并不需要真正建出这棵树，只需要维护求lca所用的fa数组和dep数组即可。另外，因为题目中说所有点都从1开始，所以一开始只要把1入队就吼了。
再说一下我的sb手残错误
我是大设备
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+10;
4 const int INF=1e9+7;
5 int first[N],nex[N<<1],to[N<<1],tot;
6 void add(int a,int b){
7 to[++tot]=b,nex[tot]=first[a],first[a]=tot;
8 }
9 vector<int> in[N];
10 int d[N],du[N],fa[N][18],v[N],w[N];
11 int Lca(int x,int y){
12 if(d[x]>d[y]) swap(x,y);
13 for(int i=16;i>=0;--i) if(d[fa[y][i]]>=d[x]) y=fa[y][i];
14 if(x==y) return x;
15 for(int i=16;i>=0;--i) if(fa[y][i]!=fa[x][i]) y=fa[y][i],x=fa[x][i];
16 return fa[x][0];
17 }
18
19 int main(){
20 int n,m,que;
21 scanf("%d%d%d",&n,&m,&que);
22 for(int i=1;i<=m;++i){
23 int x,y;
24 scanf("%d%d",&x,&y);
25 add(x,y);
26 add(y,x);
27 in[y].push_back(x);
28 du[y]++;
29 }
30 queue<int> q;
31 q.push(1);
32 // d[1]=0;
33 /*for(int i=1;i<=n;++i){
34 if(!du[i]){
35 int lca=in[i][0];
36 for(int j=1;j<in[i].size();++j) lca=Lca(lca,in[i][j]);
37 fa[i][0]=lca;
38 d[i]=d[lca]+1;
39 for(int j=1;j<=16;++j) fa[i][j]=fa[fa[i][j-1]][j-1];
40 q.push(i);
41 v[i]=1;
42 }
43 }*/
44 // for(int i=1;i<=n;++i) if(!du[i]) q.push(i)/*,du[i]=INF*/;
45 while(q.size()){
46 int x=q.front();q.pop();//cout<<x<<endl;
47 for(int i=first[x];i;i=nex[i]){
48 int y=to[i];
49 du[y]--;
50 if(!du[y]){
51 int lca=in[y][0];
52 for(int j=1;j<in[y].size();++j) lca=Lca(lca,in[y][j]);
53 fa[y][0]=lca;
54 d[y]=d[lca]+1;
55 q.push(y);
56 // du[i]=INF;
57 for(int j=1;j<=16;++j) fa[y][j]=fa[fa[y][j-1]][j-1];
58 }
59 }
60 }
61 // for(int i=1;i<=n;++i,cout<<endl) for(int j=1;j=16;++j) cout<<fa[i][j]<<" ";
62 for(int i=1;i<=que;++i){
63 int k;
64 scanf("%d",&k);
65 for(int j=1;j<=k;++j) scanf("%d",&w[j]);
66 int lca=w[1];
67 for(int j=1;j<=k;++j) lca=Lca(lca,w[j]);
68 printf("%d\n",d[lca]+1);
69 }
70 }
71 /*
72 4 3 2
73 1 2
74 2 3
75 2 4
76 2 3 4
77 2 2 4
78 */ T2 reverse：
只需要考虑最后一位是什么就好了，然后谁长就缩谁，直到他们两个一样长，就一起缩，博主打的是dfs，细节很多，很难调，所以代码就不提供了，所以就以soul神的代码为参考吧。
鸣谢soul
1 #include<bits/stdc++.h>
2 #define re register
3 using namespace std;
4 int T,a[2010],b[2010]; char s[2010]; int len;
5 inline bool cmp(){
6 if(a[0]!=b[0]) return 0;
7 for(re int i=1;i<=a[0];++i)
8 if(a[i]!=b[i]) return 0;
9 return 1;
10 }
11 signed main(){
12 scanf("%d",&T);
13 while(T--){
14 scanf("%s",s+1);len=strlen(s+1); a[0]=0;
15 for(re int i=1;i<=len;++i) a[++a[0]]=(s[i]-65);
16 scanf("%s",s+1);len=strlen(s+1); b[0]=0;
17 for(re int i=1;i<=len;++i) b[++b[0]]=(s[i]-65);
18 while(a[0]&&b[0]&&!cmp()){
19 if(a[0]>b[0])
20 while(a[0]>b[0]){
21 if(a[a[0]--])
22 for(re int i=1,lim=(a[0]>>1);i<=lim;++i) swap(a[i],a[a[0]-i+1]);
23 }
24 else if(a[0]<b[0])
25 while(b[0]>a[0]){
26 if(b[b[0]--])
27 for(re int i=1,lim=(b[0]>>1);i<=lim;++i) swap(b[i],b[b[0]-i+1]);
28 }
29 else if(a[0]==b[0]){
30 if(a[a[0]--])
31 for(re int i=1,lim=(a[0]>>1);i<=lim;++i) swap(a[i],a[a[0]-i+1]);
32 if(b[b[0]--])
33 for(re int i=1,lim=(b[0]>>1);i<=lim;++i) swap(b[i],b[b[0]-i+1]);
34 }
35 }
36 if(a[0]){for(re int i=1;i<=a[0];++i) putchar(a[i]+65); puts("");}
37 else puts("-1");
38 }
39 return 0;
40 } T3 tree：
原题，不，比原题简单，然后赛时第一个提交，成功long long见祖宗，喜提WA80。
题解是什么方法我也不知道，所以就用自己的方法说了还不是颓的以前的题解。
我们设$f[x]$表示从$x$到$fa[x]$的期望步数，$g[x]$表示从$fa[x]$到$x$的期望步数。
考虑转移$f[x]=\frac{1}{du[x]}+\sum{\frac{f[son]+1+f[x]}{du[x]}}$
挺显然的，就是他可以直接上去，也可能先下去在上去。
化简得$f[x]=du[x]+\sum{f[son]}$，一遍dfs可以求出
在来考虑g的转移$g[x]=\frac{1}{du[fa]}+\frac{1+g[x]+g[fa]}{du[fa]}+\frac{\sum{g[x]+1+f[brothers]}}{du[fa]}$
其实和f的转移也差不多就是分类讨论，可以直接下去，可以到x的兄弟节点也可以到x的父节点的父节点。
化简得$g[x]=du[fa]+g[fa]+\sum{f[bother]}$
然后树上前缀和就可以求出从根到x的期望步数了。
吐槽：
考试时知道答案一定是整数就没开double，然后，关于int，他死了最后都想到开long long了为什么不交啊，我的首杀。
1 //yuanti
2 //xingkuizuoguo
3 #include<bits/stdc++.h>
4 using namespace std;
5 const int N=1e5+10;
6 #define int long long
7 int first[N],nex[N<<1],to[N<<1],tot;
8 void add(int a,int b){
9 to[++tot]=b,nex[tot]=first[a],first[a]=tot;
10 }
11 int f[N],g[N];//f[x] x->fa[x] g[x] fa[x]->x
12 int sumg[N],sumf[N];
13 int du[N];
14 void dfs(int x,int fa){
15 f[x]=du[x];
16 for(int i=first[x];i;i=nex[i]){
17 int y=to[i];
18 if(y==fa) continue;
19 dfs(y,x);
20 f[x]+=f[y];
21 }
22 sumf[x]=f[x];
23 }
24 void dfs1(int x,int fa){
25 for(int i=first[x];i;i=nex[i]){
26 int y=to[i];
27 if(y==fa) continue;
28 g[y]=sumf[x]-f[y]+g[x];
29 dfs1(y,x);
30 }
31 }
32 void dfs2(int x,int fa){//cout<<fa<<" "<<g[fa]<<" "<<sumg[fa]<<endl;
33 sumg[x]=sumg[fa]+g[x];
34 for(int i=first[x];i;i=nex[i]){
35 int y=to[i];
36 if(y==fa) continue;
37 dfs2(y,x);
38 }
39 }
40
41 signed main(){
42 int n;
43 scanf("%lld",&n);
44 for(int i=1;i<n;++i){
45 int x,y;
46 scanf("%lld%lld",&x,&y);
47 add(x,y);
48 add(y,x);
49 du[x]++;du[y]++;
50 }
51 dfs(1,0);
52 f[1]=0;
53 dfs1(1,0);
54 sumg[1]=g[1];
55 dfs2(1,0);
56 // for(int i=1;i<=n;++i) cout<<"f["<<i<<"]=="<<f[i]<<" ";
57 // cout<<endl;
58 // for(int i=1;i<=n;++i) cout<<"g["<<i<<"]=="<<g[i]<<" ";
59 // cout<<endl;
60 for(int i=1;i<=n;++i){
61 printf("%lld.000\n",sumg[i]+1);
62 }
63 }
64 /*
65 3
66 1 2
67 2 3
68 */
转载于:https://www.cnblogs.com/leom10/p/11585961.html