10.6 测试

· · 算法·理论

T1 U432142 ૮(˶ᵔ ᵕ ᵔ˶)ა祖孙询问

m次询问每次计算x与y的lca，若x=lca(x,y),输出1；y=lca(x,y),输出2；否则输出0

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(4e4+10);
int n,m,root;
int dep[maxn],dp[maxn][31];
vector<vector<int>>e(maxn);
void dfs(int u,int f){
    dep[u]=dep[f]+1;
    for(int i(0);i<e[u].size();i++){
        int v(e[u][i]);
        if(v==f){
            continue;
        }
        dp[v][0]=u;
        for(int i(1);i<=20;i++){
            dp[v][i]=dp[dp[v][i-1]][i-1];
        }
        dfs(v,u);
    }
}
int LCA(int x,int y){
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    for(int i(20);i>=0;i--){
        if(dep[dp[y][i]]>=dep[x]){
            y=dp[y][i];
        }
    }
    if(x==y){
        return x;
    }
    for(int i(20);i>=0;i--){
        if(dp[x][i]!=dp[y][i]){
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];
} 
int main(){
//  freopen("T1.in","r",stdin);
//  freopen("T1.out","w",stdout);
    cin>>n;
    for(int i(1);i<=n;i++){
        int u,v;
        cin>>u>>v;
        if(v!=-1){
            e[u].push_back(v);e[v].push_back(u);
        }else{
            root=u;
        }
    }
    dfs(root,0);
    cin>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        if(LCA(x,y)==x){
            cout<<"1\n";
        }else if(LCA(x,y)==y){
            cout<<"2\n";
        }else{
            cout<<"0\n";
        }
    }
    return 0;
}

T2 P4281 [AHOI2008] 紧急集合 / 聚会

问：每次询问求x,y,z到某一点汇合的最短路径

对于每次询问的x,y,z，我们发现x,y,z汇合的点时x,y,z的其中一个lca

而另外两个lca相等时，唯一一个不同的lca就是等待点,因为

而最终答案=dis(a,b)+dis(b,c)+dis(a,c)\div 2

继续化简，可以得到：

dep_a+dep_b-2\times dep_{lca(a,b)}+dep_b+dep_c-2\times dep_{lca(b,c)}+dep_a+dep_c-2\times dep_{lca(a, c)}\div 2\\=\\dep_a+dep_b+dep_c-dep_{lca(a, b)}-dep_{lca(b,c)}-dep_{lca(a,c)} 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(5e5+10);
int n,m,root;
bool vis[maxn];
int dep[maxn],dp[maxn][21];
vector<vector<int>>e(maxn);
void dfs(int u,int f){
    dep[u]=dep[f]+1;
    for(int i(0);i<e[u].size();i++){
        int v(e[u][i]);
        if(v==f){
            continue;
        }
        dp[v][0]=u;
        for(int i(1);i<=20;i++){
            dp[v][i]=dp[dp[v][i-1]][i-1];
        }
        dfs(v,u);
    }
}
int LCA(int x,int y){
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    for(int i(20);i>=0;i--){
        if(dep[dp[y][i]]>=dep[x]){
            y=dp[y][i];
        }
    }
    if(x==y){
        return x;
    }
    for(int i(20);i>=0;i--){
        if(dp[x][i]!=dp[y][i]){
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];
} 
int BFS(int su,int x,int y,int z){
    int ans(0);
    queue<pair<int,int>>q;
    q.push({su,0});
    vis[su]=true;
    while(q.size()){
        pair<int,int>now(q.front());
        q.pop();
        if(now.first==x||now.first==y||now.first==z){
            ans+=now.second;
        }
        for(int i(0);i<e[now.first].size();i++){
            if(vis[e[now.first][i]]){
                continue;
            }
            vis[e[now.first][i]]=true;
            q.push({e[now.first][i],now.second+1});
        }
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i(1);i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    for(int i(1);i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        int lca1(LCA(x,y)),lca2(LCA(y,z)),lca3(LCA(x,z));
        int minn(dep[x]+dep[y]+dep[z]-dep[lca1]-dep[lca2]-dep[lca3]);
        if(lca3==lca2){
            cout<<lca1<<' ';
        }else if(lca1==lca3){
            cout<<lca2<<' ';
        }else if(lca1==lca2){
            cout<<lca3<<' ';
        }
        cout<<minn<<'\n';
    }
    return 0;
}

T3 P11477 [COCI 2024/2025 #3] 林卡树 / Stablo

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 7;
int val[maxn], p[maxn], dep[maxn];
int dp[maxn][22];
int siz[maxn], f[maxn];
vector<int> G[maxn];
void dfs(int u, int fa)
{
    siz[u] = val[u];
    dp[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = 1; i <= 20; i++)
    {
        dp[u][i] = dp[dp[u][i - 1]][i - 1];
    }
    for (int v : G[u])
    {
        if (v != fa)
        {
            dfs(v, u);
            siz[u] += siz[v];
            f[u] += f[v];
        }
    }
    f[u] += (siz[u] - val[u]);
}
int solve(int x, int y)
{
    for (int i = 20; i >= 0; i--) // 跳到的是大于的最后一个
    {
        if (dep[dp[x][i]] > dep[y]) // 说明深度还没有找到
        {
            x = dp[x][i];
        }
    }
    return x;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> val[i];
    }
    for (int i = 2; i <= n; i++)
    {
        cin >> p[i];
        G[i].push_back(p[i]);
        G[p[i]].push_back(i);
    }
    dfs(1, 0);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        if (p[x] == y) // 说明不存在z
        {
            cout << f[y] << "\n";
            continue;
        }
        int z = solve(x, y);
        cout << f[y] - (dep[x] - dep[y] - 1) * val[x] + (siz[z] - siz[x]) << "\n";
    }
    return 0;
}