10.6总结

· · 个人记录

T1

lca板子

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e4+10;
int dp[maxn][21],dep[maxn];
vector<int>g[maxn];
void addline(int u,int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
void dfs(int u,int fa){
    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 i=0;i<g[u].size();i++) {
        int v=g[u][i];
        if(v!=fa) {
            dep[v]=dep[u]+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[x][i]]>=dep[y]) {
            x=dp[x][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() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,rt;
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x,y;
        cin>>x>>y;
        if(y==-1){
            rt=x; 
        } else {
            addline(x,y);
        }
    }
    dep[rt]=1;
    dfs(rt,0);
    int m;
    cin>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        if(x==lca(x,y)) {
            cout<<1;
        } else if(y==lca(x,y)) {
            cout<<2;
        } else{
            cout<<0;
        }
        cout<<endl;
    }
    return 0;
}

T2

首先对于树上三个点汇聚在一个点上会有两种情况

可以看出，三个点要么有共同的祖先要么可以汇聚在三个点中的一个点
然后我们要求到公共点的距离，由于不知道公共点在哪里，所以我们通过公共点走到其他两个点，画记一遍路线可得走的总距离是公共点到其他三点距离的两倍，即公共点到其他点的距离为

(dis(a,b)+dis(b,c)+dis(a,c))/2

然后因为dis(a,b)=dep[a]+dep[b]-2*dep[a]*dep[b]得其他点到公共点的距离为dep[a]+dep[b]+dep[c]-dep[lca(a,b)]-dep[lca(b,c)]-dep[lca(a,c)] 而上述的值是定值，接下来只需要确定在三个祖先中哪个是最优的就行，这三个点到达lca和另外两个lca不一样的点时候的距离最小

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+7;
vector<int>g[maxn];
void addline(int u,int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
int dep[maxn],dp[maxn][21];
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;
    dp[u][0]=fa;
    for(int i=1;i<=20;i++) {
        dp[u][i]=dp[dp[u][i-1]][i-1];
    }
    for(int i=0;i<g[u].size();i++) {
        int v=g[u][i];
        if(v!=fa) {
            dep[v]=dep[u]+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() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        addline(u,v);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++) {
        int x,y,z,ans;
        cin>>x>>y>>z;
        int l1=lca(x,y),l2=lca(y,z),l3=lca(z,x);
        if(l1==l2) {
            ans=l3;
        } else if(l2==l3) {
            ans=l1;
        } else if(l1==l3){
            ans=l2;
        }
        cout<<ans<<' '<<dep[x]+dep[y]+dep[z]-dep[l1]-dep[l2]-dep[l3]<<'\n';
    }
    return 0;
}

T3

首先要翻译题面的行为 懒得敲字了自己看图

将x作为原来y中包含x的子树的根，原来的根变为它的儿子 而我们不难发现，x儿子的深度是不变的而变的只有z和x的深度
首先如果x就是y的直接儿子说明转换如同没转换一样，可以直接输出f[y]
否则我们可以看见，变化的只有x和z的深度，x深度变小而z的深度变大的数值相同，意味着需要-siz[x]+siz[z]，x的深度变成了dep[y]+1则意味着点权和边权的乘积增加(dep[y]-dep[x]-1)*v[x] 所以位移后的f(y')=f(y)+siz[z]-siz[x]-(dep[y]-dep[x]-1)*v[x]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
const int maxn = 5e5+10;
vector<int>g[maxn];
int v[maxn], p[maxn], dep[maxn];
int dp[maxn][22];
int siz[maxn], f[maxn];
void addline(int u,int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
void dfs(int u,int fa){
    siz[u] = v[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 i=0;i<g[u].size();i++) {
        int v=g[u][i];
        if(v!=fa) {
            dfs(v, u);
            siz[u] += siz[v];
            f[u] += f[v];
        }
    }
    f[u] += (siz[u] - v[u]);
}
int lca(int x,int y){
    for(int i=20;i>=0;i--) {
        if(dep[dp[x][i]]>dep[y]) {
            x=dp[x][i];
        }
    }
    return x;
}
int dist(int x,int y) {
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int count(int x,int y) {
    return dist(x,y)*v[x];
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>v[i];
    }
    for(int i=2;i<=n;i++) {
        cin>>p[i];
        addline(p[i],i);
    }
    dfs(1,0);
    while(q--) {
        int x,y;
        cin>>x>>y;
        if(p[x]==y){
            cout<<f[y]<<'\n';
            continue;
        }
        int z=lca(x,y);
        cout << f[y] - (dep[x] - dep[y] - 1) * v[x] + (siz[z] - siz[x]) << "\n";
    }
    return 0;
}