【LCA+树上距离+手推样例观察结论】CF1304 E. 1-Trees and Queries

红太狼 2024-03-16 09:41 2阅读 0赞

**感觉CF的题，很多都是手推样例，然后猜结论，结论搞出来了剩下就不难了**

**样例真的，很重要啊QwQ**

题意：

![e7f9d4f4533e46cab5bd184e5fc9620c.png][]

![2cb50ad80c4a4fabbcef01168976651c.png][]

思路：

一开始想的是

树上加一条边，那就是个基环树

a到b原来的路径长度是固定的，因此如果原来的长度D!=K，那就必须要通过新加的边了

那就是求出新加边之后a到b的距离

但是突然注意到题目还有一个条件：边可以重复走

那么就自然想到了奇偶性：

![4f86734cfe524d4cb5217f4d96df51b1.png][]

![7aa3da91732a4466a665ff27eb1a67fb.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int tot=0;
    int N,Q,u,v,a,b,x,y,K;
    int dep[mxn],F[mxn][33],head[mxn];
    
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void dfs1(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;
    		dfs1(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)];
    }
    bool check(int a,int b){
    	return a>=b&&(a-b)%2==0;
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs1(1,0);
    	cin>>Q;
    	while(Q--){
    		cin>>x>>y>>a>>b>>K;
    		int d1=dist(a,b);
    		int d2=dist(a,x)+1+dist(y,b);
    		int d3=dist(a,y)+1+dist(x,b);
    		if(check(K,d1)||check(K,d2)||check(K,d3)) cout<<"YES"<<'\n';
    		else cout<<"NO"<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[e7f9d4f4533e46cab5bd184e5fc9620c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/def6adb740f54f9f84dfd0ac95e6e579.png
[2cb50ad80c4a4fabbcef01168976651c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/fa1f42d16ffb44b2a319e4b5c7dca4c9.png
[4f86734cfe524d4cb5217f4d96df51b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9d2f51ac935f4985837bdf115d4d3f4f.png
[7aa3da91732a4466a665ff27eb1a67fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e2809dfed0ec4b66a2febc8cd04993ee.png