cf620 div2 abcde

A Two Rabbits standard input/output 1 s, 256 MB Submit Add to favourites x12905

　　如果两个兔子之间的差值为 a+b 的倍数则有解，否则无解

B Longest Palindrome standard input/output 1 s, 256 MB Submit Add to favourites x9945

//　　He has n distinct strings of equal length m.

　　如果字符串的回文串存在则加入结果串的前后，

　　如果自身就是回文串的话就作为结果串的中间串，
　　因为每个串都是不同的所以自身是回文串最多只会有一次出现只需要标记一次即可，
　　可以把每次的字符串加入一个map 用以记录字符串是否出现，
//　　当时做题的时候没认真看题想太多，老是想要是自身为回文串出现多次该怎么解决越想越复杂 zz

C Air Conditioner standard input/output 1 s, 256 MB Submit Add to favourites x7234

　　把每次能达到的最低温度和最高温度与 l[i] 和 h[i] 两个区间比较如果有交集，则更新下最低温度和最高温度，当没有交集的时候表示无解

D Shortest and Longest LIS standard input/output 3 s, 256 MB Submit Add to favourites x3432

// 首先要满足条件可以min LIS 是最长的连续小于的序列，所以可以从 n开始分配每次满足部分区间的大小关系
// 因为要最大化 LIS 所以要从 1 开始分配，每次的大小关系都为一段连续的自然数
// 每次根据大小关系分配连续的自然数，
// min LIS 就从 n 开始分配，这样区间重合最小
// max LIS 就从 1 开始分配这样区间重合最大

E 1-Trees and Queries standard input/output 4 s, 512 MB Submit Add to favourites x2370

题意：给你一颗树 n个顶点 n-1条边，进行 q 次询问，问经过添加 x -> y 边后 a->b 是否有一条路径长度为 k，有输出 YES 否则输出 NO

首先这条路径可以重复点也就是说 1-3 最短路径长为3 那么 1-3可以为3+2*x x为任意值，可以在 1 3之间来回走动只需保证起点为1 终点为3 即可

所以问题就转化为求a到b 的是否有一条与k同奇偶性且小于等于k的路径

a到b的最小路径可以为 a直接到b 或者 a->x->y->b 或者 a->y->x>b
所以只需求解这三条路径与k的关系，可以把这个图当成建成以1为根的树，然后求

lca_len(a, b); lca_len(a, x) +1 +lca_len(y, b), lca_len(a, y) + lca_len(x, b) + 1;

相当于每次求两点距离的时候就是求跳到同一个根节点需要的步数， depth大的先倍增跳到dep小的节点的下一层 (直接跳到同一层容易误判) 1<< i (depth大的一个人跳)，然后两节点一起倍增跳 1<<(i+1) （两个人一起跳，步数加倍）

至于如果不会求LCA的话，可以看看这个

求LCA的话就是用倍增的算法，先构造一棵树且 dp每个节点跳2¹ 2² 2³.…… 步的祖先，然后depth大的先倍增跳到同一层，然后两节点一起倍增跳

F1 Animal Observation (easy version) standard input/output 3 s, 512 MB Submit Add to favourites x824
F2 Animal Observation (hard version) standard input/output 3 s, 512 MB Submit Add to favourites x624

#include <bits/stdc++.h> // cf 620div2
using namespace std;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define _for(i,a,b) for(int i = (a); i < (b); i++) 
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)

void taskA() {
    int t;
    cin >> t;
    while(t--) {
        int x,y,a,b; 
        cin >> x >> y >> a >> b;
        if((y-x)%(a+b) == 0) {
            cout << (y-x)/(a+b) << "
";
        } else cout << "-1
";
    }
    return;
}

void taskB() {
    int n,m; cin >> n >> m;
    string a,b,c;
    map<string, int> mp;
    _for(i,0,n) {
        string s; cin >> s;
        string t = s;
        mp[s]++;
        reverse(all(t));
        if(s == t) {
            if(s.size() > c.size()) c = s;
        } else {
            if(mp.count(t) != 0) {
                a += s;
                b += s;
                mp.erase(t);
            }
        }
    }
    reverse(all(b));
    cout << a.size()+b.size()+c.size() << "
";
    cout << a+c+b << "
";
    return;
}

void taskC(){
    int t; cin >> t;
    while(t--) {
        int n,m; cin >> n >> m;
        vector<int> t(n+1), l(n+1), h(n+1);
        _rep(i,1,n) cin >> t[i] >> l[i] >> h[i];
        int f = 0, x = m, y = m;
        t[0] = 0;
        _rep(i,1,n) {
            int z = t[i]-t[i-1];
            x -= z;
            y += z;
            if(l[i]>y or x>h[i]) {f = 1; }
            else x = max(x, l[i]), y = min(y, h[i]);
        }
        cout << (f ? "NO
" : "YES
" );
    } return;
}

void taskD(){
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        string s; cin >> s;
        vector<int> ans(n);
        int last = 0, num = n;
        _for(i,0,n) {
            if(s[i] == '>' || i == n-1)
                {
                    for(int j = i; j >= last; j--) 
                        ans[j] = num--;
                    last = i+1;
                }
        }
        _for(i,0,n) cout << ans[i] << " 
"[i==n-1];

        last = 0, num = 1;
        _for(i,0,n) {
            if(s[i] == '<' || i == n-1) {
                for(int j = i; j >= last; j--)
                    ans[j] = num++;
                last = i+1;
            }
        }
        _for(i,0,n) cout << ans[i] << " 
"[i==n-1];
    }
    return;
}

const int N = 1e5+100; //https://codeforces.com/contest/1304/problem/E
const int LIM = 17; // cf 620div2

vector<int> g[N];
int par[N][LIM+1], depth[N], lg[N];

void build(int cur, int p) {
    depth[cur] = depth[p]+1;
    par[cur][0] = p;
    _rep(i,1,LIM) 
        par[cur][i] = par[par[cur][i-1]][i-1];
    for(auto it : g[cur]) 
        if(it != p) 
            build(it, cur);
    return;
}
int lca_len(int a, int b) {
    int len = 0;
    if(depth[a] > depth[b]) swap(a, b);
    while(depth[a] < depth[b]) {
        int x = lg[depth[b]-depth[a]]-1;
        b = par[b][x];
        len += (1<<x);
    }
    if(a == b) return len;
    for(int i = lg[depth[a]]; i >= 0; i--) {
        if(par[a][i] != par[b][i]) {
            a = par[a][i]; 
            b = par[b][i];
            len += (1<<(i+1));
        }
    }
    return len+2;
}
void taskE() {
    int n; cin >> n;
    _for(i,1,n) {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    _rep(i,1,n) lg[i] = lg[i-1]+(1<<lg[i-1] == i);
    build(1, 0);
    int q; cin >> q;
    while(q--) {
        int x,y,a,b,k; cin >> x >> y >> a >> b >> k;
        int x1 = lca_len(a, b);
        int x2 = lca_len(a, x)+lca_len(y, b) +1;
        int x3 = lca_len(a, y)+lca_len(x, b) +1;
        int ans = INT_MAX;
        if(x1%2 == k%2) ans = x1;
        if(x3%2 == k%2) ans = min(ans, x3);
        if(x2%2 == k%2) ans = min(ans, x2);
        cout << (ans <= k ? "YES
" : "NO
");
    }
    return;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    //taskA();
    //taskB();
    //taskC();
    //taskD();
    taskE();
    //taskF();
    return 0;
}