首页 > 其他分享 >树上跳棋

树上跳棋

时间:2024-05-12 21:52:55浏览次数:20  
标签:lcm int 跳棋 dep read ans 树上 d2

题目链接

`戳我

\(Solution\)

对于一个点如果能够被跳到当且仅当这个点的深度\(mod\)一次跳的长度等于起始节点\(mod\)一次跳的长度
假设能够被\(p1,p2\)两个点都能到达的点为\(z\)需要满足以下条件

\[dep[z]<=dep[lca] \]

\[dep[z]\equiv dep[p1]\ (mod \ d1) \]

\[dep[z]\equiv dep[p2]\ (mod \ d2) \]

下面那两个同余的限制可以用\(excrt\)(扩展中国剩余定理)算出最小的\(dep[z]\)
然后满足的\(dep[z]\)就是\(dep[z]+k*lcm(d1,d2)\quad k \in N^*\)
通过这个可以算出满足\(dep[z]<=dep[lca]\)最大的\(dep[z]\)即两个棋子的最近的重合节点
对于\(-1\)的情况即需要判断一下是否有解和是否存在\(dep[x]<=dep[lca]\)即可

\(Code\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = getchar();
    return f * x;
}
struct node {
    int to, next;
} a[400010];
int head[200010], cnt;
int f[200010][21], dep[200010];
void add(int x, int y) {
    a[++cnt].next = head[x];
    head[x] = cnt;
    a[cnt].to = y;
}
void dfs(int x, int fa) {
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;
    for(int i = 1; i <= 20; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = head[x]; i; i = a[i].next) {
        int v = a[i].to;
        if(v == fa)
            continue;
        dfs(v, x);
    }
}
int lca(int x, int y) {
    if(dep[x] > dep[y])
        swap(x, y);
    for(int i = 20; i >= 0; i--)
        if(dep[f[y][i]] >= dep[x])
            y = f[y][i];
    if(x == y)
        return x;
    for(int i = 20; i >= 0; i--)
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int jump(int x, int depth) {
    for(int i = 20; i >= 0; i--)
        if(dep[f[x][i]] >= depth)
            x = f[x][i];
    return x;
}
int exgcd(int a, int b, int& x, int& y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, x, y);
    int X = x, Y = y;
    x = Y, y = X - a / b * Y;
    return gcd;
}
int ksm(int a, int b, int p) {
    int ans = 0;
    while(b) {
        if(b & 1)
            ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ans;
}
int m[10], A[10];
int find(int X, int Y, int a, int b) {
    A[1] = X, A[2] = Y;
    m[1] = a, m[2] = b;
    int lcm = m[1], ans = A[1] % m[1];
    int c = ((A[2] - ans) % m[2] + m[2]) % m[2], x, y;
    int gcd = exgcd(lcm, m[2], x, y);
    int k = ksm(x, c / gcd, m[2] / gcd);
    ans += lcm * k;
    lcm *= m[2] / gcd;
    ans = (ans % lcm + lcm) % lcm;
    return ans;
}
signed main() {
    int n = read(), x, y;
    for(int i = 1; i < n; i++)
        x = read(), y = read(), add(x, y), add(y, x);
    int q = read();
    dfs(1, 0);
    while(q--) {
        int x = read(), d1 = read(), y = read(), d2 = read();
        int Lca = lca(x, y), lcm = d1 * d2 / __gcd(d1, d2);
        int minx = find(dep[x] % d1, dep[y] % d2, d1, d2);
        if(minx == 0)
            minx += lcm;
        if(minx % d1 != dep[x] % d1 || minx % d2 != dep[y] % d2) {
            puts("-1");
            continue;
        }
        if(minx > dep[Lca]) {
            puts("-1");
            continue;
        }
        int depth = (dep[Lca] - minx) / lcm * lcm + minx;
        cout << jump(x, depth) << "\n";
    }
}

标签:lcm,int,跳棋,dep,read,ans,树上,d2
From: https://www.cnblogs.com/hbxblog/p/18188255

相关文章

  • [笔记](更新中)树形dp-中(树上背包)
    树上背包是树形dp的常见模型,通常是分组背包的变形。引入:二叉苹果树P2015二叉苹果树题意简述:在一个二叉树中,每个边有一个权值。我们要保留\(Q\)条边组成的连通分量(必须包含根节点),求边权和最大值。我们思考,从节点\(1\)(根节点)开始保留\(Q\)条边,最大答案是什么?我们分出\(3\)种......
  • 树上求一个点邻域信息的一种简单求法
    有人说,直接点分树,力大砖飞,非常不错!实际上这种做法非常的垃圾,很多时候我们使用点分树,一定是不得不使用点分树,比如模板题,强制在线,非常的恶心,所以我们使用点分树。而点分树是否必要呢?既然你能看到这篇blog,他肯定是不必要的!我们今天来发掘dsuontree的美妙性质,让他求解这个问题!然......
  • 树上差分等操作
    树链剖分&树上差分有一些相关的树上操作主要是写可持久化的时候的时候发现\(lxl~Day~5\)中有些东西根本不是可持久化...树链剖分主要记录重链剖分,不讲基本原理,只是题解CF536ETavasonthePath好像并没有可持久化,但是树剖先考虑在序列上做这个问题,......
  • 树上背包
    简介树上背包,顾名思义,就是在树上做背包。比如这道题:收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号......
  • 洛谷2664树上游戏-点分治
    link:https://www.luogu.com.cn/problem/P2664lrb有一棵树,树的每个节点有个颜色。给一个长度为\(n\)的颜色序列,定义\(s(i,j)\)为\(i\)到\(j\)的颜色数量。以及\[sum_i=\sum_{j=1}^ns(i,j)\]现在他想让你求出所有的\(sum_i\)。一个暴力的想法:因为是求和,所以可以拆......
  • 树上背包
    就是在树上做背包,通常把子树的最优值当成一个一个元素,合并他们。\(u\tov\)的边。收集型伪代码for(inti=sz[u];~i;i--){ for(intj=min(sz[v],i);~j;j--){ dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j]); }}扩散型伪代码for(inti=sz[u];~i;......
  • 树上最小点覆盖的一类问题
    前言关于下文中\(lim\)较小的最小点覆盖问题,我们通常会对每个节点设出若干状态转移,而下文所说的问题是此问题的通解,但复杂度为平方级别题意给定一棵无根有权树,每个点建消防站都有一定代价\(c\),每个点都有一个限制\(lim\),表示离它最近的消防站的最大距离。求让所有点安全的......
  • [BZOJ4358]permu树上莫队
    先放代码晚上补(争取)#include<bits/stdc++.h>#definefo(x,y,z)for(int(x)=(y);(x)<=(z);(x)++)#definefu(x,y,z)for(int(x)=(y);(x)>=(z);(x)--)typedeflonglongll;usingnamespacestd;inlineintqr(){ charch=getchar();intx=0,f=1; for(;ch<&......
  • (复习)树上启发式合并(dsu on tree)入门U41492树上数颜色
    主要思想是树的重轻儿子之分使得时间复杂度为o(nlogn),神奇欲深入了解的这里:https://oi-wiki.org/graph/dsu-on-tree/点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedefstructedge//边结构体{intto,next;}EDGE;//边相关数组EDGEe[100001<<1];......
  • 贡献法之求树上上任意两点间的路径之和
    一图胜千言开始造火箭虽然我们可以求出,总共的dis(i,j),但分散到每一个小dis(i,j),由于存在向上取整操作,我们需要求出将每一个小dis(i,j)给补成k的倍数的补数之和!此处我们采用树形dp。dp[u][j]表示以u的子节点到根节点root的距离对k取余的值为j的点的个数我们如何求树上任意两......