【EOJ Monthly】2021.2

1.比賽鏈接：EOJ Monthly 2020.2
2.比賽情況：A題磕磕碰碰也算是拿了100（看錯了從任意起點出發）；B題圖論蒟蒻選手直接把直鏈和樹都當成樹，寫一個樸素LCA暴力騙38分閃人；C題直接在10！下找到所有可能的排列去構造線段樹，然后判斷是否滿足所給定的區間騙23分閃人；D一分沒得，
3.比賽總結：感覺B題沒做出來對不起自己刷的PAT…

A：昔我往矣

??這道題我的做法是采用LCA先找兩個結點的最近公共祖先，然后不斷地往里面加入新的點，①很明顯，第一輪兩個結點需要走過的距離是 d i s t [ A ] + d i s t [ B ] ? 2 ? d i s t [ l c a ( A , B ) ] dist[A]+dist[B]-2*dist[lca(A,B)] dist[A]+dist[B]?2?dist[lca(A,B)]; ②但我們找到了前 i i i個結點的LCA時，考慮如何加入第 i + 1 i+1 i+1個結點，我們找前 i i i個結點的最近公共祖先結點 l c a i lca_i lcai?和第 i + 1 i+1 i+1個結點的最近公共祖先 l c a i + 1 lca_{i+1} lcai+1?，然后判斷：（i）如果 l c a i = l c a i + 1 lca_i=lca_{i+1} lcai?=lcai+1?，那說明第 i ? 1 i-1 i?1個結點在以 l c a i lca_i lcai?為根節點的子樹當中，我們要往前搜索所有的結點，找到與當前第 i + 1 i+1 i+1個結點的所有最近公共祖先結點中，層次最深的那一個 t m p tmp tmp，然后貢獻加上 d i s t [ a [ i + 1 ] ] ? d i s t [ t m p ] dist[a[i+1]]-dist[tmp] dist[a[i+1]]?dist[tmp]（這樣才不會造成路徑的重復計數）；（ii）如果 l c a i ≠ l a c i + 1 lca_i\ne lac_{i+1} lcai??=laci+1?，說明第 i + 1 i+1 i+1個結點不在以 l c a i lca_i lcai?為根節點的子樹中，直接計算路徑即可，

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=5e4+5;
int n,m;
struct Edge{
	int to,next,weight;
}e[maxn<<1];
int head[maxn],tot=0,a[10],dis[maxn];
void addedge(int x,int y,int w)
{
	e[++tot].to=y;
	e[tot].weight=w;
	e[tot].next=head[x];
	head[x]=tot;
}
int fa[maxn][25],lg[maxn],dep[maxn];
void DFS(int now,int father,int dist)
{
	fa[now][0]=father,dep[now]=dep[father]+1;
	dis[now]=dist;
	for(int i=1;(1<<i)<=dep[now];++i)
		fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=e[i].next)
		if(e[i].to!=father) DFS(e[i].to,now,dist+e[i].weight);
} 
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y) return x;
	for(int k=lg[dep[x]]-1;k>=0;--k)
		if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
	return fa[x][0];
}
void init_lg(){for(int i=1;i<=n;++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);} 
int main()
{
	close;cin>>n;
	for(int i=0;i<n-1;++i)
	{
		int x,y,w;cin>>x>>y>>w;
		addedge(x,y,w);addedge(y,x,w);
	}
	init_lg();DFS(0,-1,0);cin>>m;
	while(m--)
	{
		for(int i=0;i<5;++i) cin>>a[i];
        int A=a[0],B,minnum=0;
		for(int i=1;i<=4;++i)
		{
			B=a[i];
			int tmp=LCA(A,B);
            if(tmp==A){
                int now=A;
                for(int j=0;j<i;++j){
                    int cur_num=LCA(a[i],a[j]);
                    if(dep[cur_num]>dep[now]) now=cur_num;
                }
                minnum+=dis[B]-dis[now];
            }
            else{
                minnum+=dis[A]+dis[B]-dis[tmp]*2;
                A=tmp;
            }
		}
		cout<<minnum<<"\n";
	}
}

B：楊柳依依

??考察最短路問題，但要求解最短路中經過結點 i i i的所有路徑的條數，
??兩遍BFS求最短路，第一遍BFS找到起點 s s s到點 i i i的方案數，第二遍BFS找到終點 t t t到起點 i i i的方案數，相乘就是總的可能路線，注意寫法（第一遍BFS會給一些不在最短路徑上的結點也賦值了，第二遍就一定要保證不在最短路徑上的點值一定是0），

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=5e3+100;
const double eps=1e-6;
vector<int> G[maxn];
int num1[maxn],num2[maxn],d[maxn];
double ans[maxn];
int main()
{
	close;int n,m;cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int k;cin>>k;
	for(int i=1;i<=k;++i)
	{
		int x,y;cin>>x>>y;
		memset(num1,0,sizeof(num1));
		memset(num2,0,sizeof(num2));
		memset(d,0,sizeof(d));
		queue<int> q;
		d[x]=0,num1[x]=1;q.push(x);
		while(!q.empty()){
			int cur=q.front();q.pop();
			if(cur==y) break;
			for(auto tmp:G[cur]){
				if(num1[tmp]==0) q.push(tmp),d[tmp]=d[cur]+1;
				if(d[tmp]==d[cur]+1) num1[tmp]+=num1[cur]; 
			}
		}
		while(!q.empty()) q.pop();
		num2[y]=1;q.push(y);
		while(!q.empty()){
			int cur=q.front();q.pop();
			if(cur==x) break;
			for(auto tmp:G[cur]){
				if(d[tmp]==d[cur]-1){
					if(num2[tmp]==0) q.push(tmp);
					num2[tmp]+=num2[cur];
				}
			}
		}
		for(int i=0;i<n;++i) ans[i]+=1.0*num2[i]*num1[i]/num2[x];
	}
	int pos=0;
	for(int i=1;i<n;++i) if(ans[i]-ans[pos]>=eps) pos=i;
	cout<<pos;
}

C：今我來思

D：雨雪霏霏