【树链+EXGCD】杭电多校第一场 A

古城微笑少年丶 2024-03-17 21:45 69阅读 0赞

[1001 Hide-And-Seek Game (hdu.edu.cn)][1001 Hide-And-Seek Game _hdu.edu.cn]

题意：

给定一棵树和两条路径，每条路径都有起点和终点，起始时起点有人，每隔一秒都会往终点走一步，会从起点走向终点再会起点这样不断地周期性地走，让你求一点，使得两个人能在这点相遇且花的时间最少

![45205f1d536d4938a84b9e3cca77e049.png][]

思路：

首先答案一定是两条路径相交的点中的一个，因此可以把一条路径标记一下，然后对于另一条路径去check是否重合

对于树链的操作，只需要求出LCA，分成两部分，暴力跳即可

找出重合的点，即可能是答案的点之后，需要处理怎么样才能使时间最少

![e87b43836b8c40ed9d7e882e788d95c5.png][]

比赛的时候只是分成四种情况讨论，并没有解方程，赛后调了很久也没有全对，但是只是几个数据没过，也根本调不出来

那就这样吧，反正大部分都对了 （

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e3+10;
    const int mxe=3e3+10;
    const int Inf=1e18;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,M,Q,u,v,s1,t1,s2,t2,k1,k2;
    int tot=0;
    int a[mxn];
    int head[mxn],dep[mxn],F[mxn][33];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
            dep[i]=0;
            for(int j=0;j<=30;j++) F[i][j]=0;
    	}
    }
    void dfs(int u,int fa){
        dep[u]=dep[fa]+1;
        F[u][0]=fa;
        for(int j=1;j<=30;j++) F[u][j]=F[F[u][j-1]][j-1];
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
        }
    }
    int lca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        for(int j=30;j>=0;j--){
            if(dep[F[u][j]]>=dep[v]){
                u=F[u][j];
            }
        }
        if(u==v) return u;
        for(int j=30;j>=0;j--){
            if(F[u][j]!=F[v][j]){
                u=F[u][j];
                v=F[v][j];
            }
        }
        return F[u][0];
    }
    int dist(int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    }
    int exgcd(int a,int b,int &k1,int &k2){
        if(!b){
            k1=1;k2=0;
            return a;
        }
        int d=exgcd(b,a%b,k2,k1);
        k2-=(a/b)*k1;
        return d;
    }
    void solve(){
    	cin>>N>>M;
    	G_init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        while(M--){
            cin>>s1>>t1>>s2>>t2;
            int G=lca(s1,t1);
            int s11=s1,t11=t1;
            if(dep[s11]<dep[t11]) swap(s11,t11);
            int cur=s11;
            map<int,int> mp;
            //链上的点
            int L1=0,L2=0;
            while(cur!=G){
                mp[cur]=1;
                L1++;
                cur=F[cur][0];
            }
            cur=t11;
            while(cur!=G){
                mp[cur]=1;
                L1++;
                cur=F[cur][0];
            }
            mp[G]=1;
            //L1++;
            int s22=s2,t22=t2;
            if(dep[s22]<dep[t22]) swap(s22,t22);
            cur=s22;
            int G2=lca(s22,t22);
            vector<int> V;
            //路径交点
            while(cur!=G2){
                L2++;
                if(mp.count(cur)) V.push_back(cur);
                cur=F[cur][0];
            }
            cur=t22;
            while(cur!=G2){
                L2++;
                if(mp.count(cur)) V.push_back(cur);
                cur=F[cur][0];
            }
            if(mp.count(G2)) V.push_back(G2);
            //L2++;
            if(V.empty()){
                cout<<-1<<'\n';
                continue;
            }
            set<pair<int,int> > ansv;
            for(auto x:V){
                //1==3
                int D1=exgcd(2*L1,-2*L2,k1,k2);
                int N2=dist(s2,x)-dist(s1,x);
                k1=k1*N2/D1;
                if(N2%D1==0){
                    k1=k1*N2/D1;
                    //包含0这个解，不需要%r+r
                    ansv.insert({dist(s1,x)+2*k1*L1,x});
                }
                //1==4
                int D2=exgcd(2*L1,-2*L2,k1,k2);
                int N3=L2+dist(t2,x)-dist(s1,x);
                k1=k1*N3/D2;
                if(N3%D2==0){
                    k1=k1*N3/D2;
                    ansv.insert({dist(s1,x)+2*k1*L1,x});
                }
                //2==3
                int D3=exgcd(2*L1,-2*L2,k1,k2);
                int N4=dist(s2,x)-L1-dist(x,t1);
                k1=k1*N4/D3;
                if(N4%D3==0){
                    k1=k1*N4/D3;
                    ansv.insert({L1+dist(x,t1)+2*k1*L1,x});
                }
                //2==4
                int D4=exgcd(2*L1,-2*L2,k1,k2);
                int N5=L2+dist(t2,x)-L1-dist(x,t1);
                k1=k1*N5/D4;
                if(N5%D4==0){
                    k1=k1*N5/D4;
                    ansv.insert({L1+dist(x,t1)+2*k1*L1,x});
                }
            }
            if(ansv.empty()) cout<<-1<<'\n';
            else{
                cout<<(*ansv.begin()).second<<'\n';
            }
        }
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

标程：

#include<cstdio>
    #include<algorithm>
    #include<cmath>
    #define M 5005
    using namespace std;
    struct E{
    	int to,nx;
    }edge[M<<1];
    int tot,head[M];
    void Addedge(int a,int b){
    	edge[++tot].to=b;
    	edge[tot].nx=head[a];
    	head[a]=tot;
    }
    int sz[M],son[M],top[M],dep[M];
    int Dfn[M],Low[M],tot_dfs;
    int fa[M];
    void dfs(int now){
    	Dfn[now]=++tot_dfs;
    	sz[now]=1;son[now]=0;
    	for(int i=head[now];i;i=edge[i].nx){
    		int nxt=edge[i].to;
    		if(nxt==fa[now])continue;
    		fa[nxt]=now;
    		dep[nxt]=dep[now]+1;
    		dfs(nxt);
    		sz[now]+=sz[nxt];
    		if(sz[son[now]]<sz[nxt])son[now]=nxt;
    	}
    	Low[now]=tot_dfs;
    }
    void dfs_top(int now){
    	if(son[now]){
    		top[son[now]]=top[now];
    		dfs_top(son[now]);
    	}
    	for(int i=head[now];i;i=edge[i].nx){
    		int nxt=edge[i].to;
    		if(nxt==fa[now]||nxt==son[now])continue;
    		top[nxt]=nxt;
    		dfs_top(nxt);
    	}
    }
    int LCA(int a,int b){
    	while(top[a]!=top[b]){
    		if(dep[top[a]]<dep[top[b]])b=fa[top[b]];
    		else a=fa[top[a]];
    	}
    	return dep[a]<dep[b]?a:b;
    }
    bool In(int x,int y){
    	return Dfn[y]<=Dfn[x]&&Dfn[x]<=Low[y];
    }
    int mark[M];
    struct Point{
    	int a,b;
    };
    Point Data[M][2];
    int exgcd(int a,int b,int &x,int &y){
    	int d=a; if(b==0) x=1,y=0; else{
    		d=exgcd(b,a%b,y,x),y-=a/b*x;
    	}
    	return d;
    }
    int Get_ans(Point p1,Point p2){
    	int val=p2.b-p1.b;
    	val%=p2.a;
    	while(val<0)val+=p2.a;
    	while(val>p2.a)val-=p2.a;
    	int a=p1.a,b=-p2.a;
    	int x,y,d=exgcd(a,b,x,y);
    	if(val%d!=0)return 1e9;
    	x*=val/d;y*=val/d;
    	int p=b/d,q=a/d;
    	if(x<0){
    		int k=ceil((1.0-x)/p);
    		x+=p*k,y-=q*k;
    	}else if(x>=0){
    		int k=(x-1)/p;
    		x-=p*k,y+=q*k;
    	}
    	return a*x+p1.b;
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		int n,m;
    		tot=0;
    		scanf("%d%d",&n,&m);
    		tot_dfs=0;
    		for(int i=1;i<=n;i++)head[i]=mark[i]=0;
    		for(int i=1;i<n;i++){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			Addedge(a,b);
    			Addedge(b,a);
    		}
    		dfs(1);
    		top[1]=1;
    		dfs_top(1);
    		for(int step=1;step<=m;step++){
    			int a,b,c,d;
    			scanf("%d%d%d%d",&a,&b,&c,&d);
    			if(a==c){printf("%d\n",a);continue;}
    			int x1=LCA(a,b),x2=LCA(c,d);
    			if(dep[x1]>dep[x2]){
    				swap(a,c);
    				swap(b,d);
    				swap(x1,x2);
    			}
    			if(!In(a,x2)&&!In(b,x2)){
    				puts("-1");
    				continue;
    			}
    			int d1=dep[a]+dep[b]-2*dep[x1],d2=dep[c]+dep[d]-2*dep[x2];
    			int p=a;
    			while(1){
    				Data[p][0]=(Point){2*d1,dep[a]-dep[p]};
    				Data[p][1]=(Point){2*d1,2*d1-(dep[a]-dep[p])};
    				mark[p]=step;
    				if(p==x1)break;
    				p=fa[p];
    			}
    			p=b;
    			while(p!=x1){
    				Data[p][0]=(Point){2*d1,d1-(dep[b]-dep[p])};
    				Data[p][1]=(Point){2*d1,d1+(dep[b]-dep[p])};
    				mark[p]=step;
    				p=fa[p];
    			}
    			
    			int ans_val=1e9,ans=-1;
    			p=c;
    			while(1){
    				Point p1=(Point){2*d2,dep[c]-dep[p]};
    				Point p2=(Point){2*d2,2*d2-(dep[c]-dep[p])};
    				if(mark[p]==step){
    					int res=1e9;
    					res=min(min(Get_ans(p1,Data[p][0]),Get_ans(p1,Data[p][1])),min(Get_ans(p2,Data[p][0]),Get_ans(p2,Data[p][1])));
    					if(res<ans_val){
    						ans_val=res;
    						ans=p;
    					}
    				}
    				if(p==x2)break;
    				p=fa[p];
    			}
    			p=d;
    			while(p!=x2){
    				Point p1=(Point){2*d2,d2-(dep[d]-dep[p])};
    				Point p2=(Point){2*d2,d2+(dep[d]-dep[p])};
    				if(mark[p]==step){
    					int res=1e9;
    					res=min(min(Get_ans(p1,Data[p][0]),Get_ans(p1,Data[p][1])),min(Get_ans(p2,Data[p][0]),Get_ans(p2,Data[p][1])));
    					if(res<ans_val){
    						ans_val=res;
    						ans=p;
    					}
    				}
    				p=fa[p];
    			}
    			printf("%d\n",ans);
    		}
    	}
    	return 0;
    }

[1001 Hide-And-Seek Game _hdu.edu.cn]: https://acm.hdu.edu.cn/contest/problem?cid=1094&pid=1001
[45205f1d536d4938a84b9e3cca77e049.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/df4daedf89234764bb9226114ec9d396.png
[e87b43836b8c40ed9d7e882e788d95c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/794bd374ed8e4af7956e84ef60121631.png