树

kyrixn · 2018-07-23 10:01:14 · 个人记录

嘿嘿在宿舍悄咪咪发一手blog

先是树的重心

重心的性质：

以重心为根，所有子树的大小都不超过整棵树的一半（定义）
把两棵树联通，新树的重心在原两树重心连线上
一棵树最多有两个重心

求以树上每个节点为根的子树的重心：

dei码：

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n,q;
int f[300003],ans[300003],num[300003];
vector<int> g[300003];

void dfs(int u) {
    //cout <<u<<endl;
    //for(int i=1; i<=n; i++) cout <<ans[i]<<" ";
    //cout <<endl;
    num[u] =1;
    ans[u] =u;

    int prop=0;
    for(int i=0; i<g[u].size(); i++) {
        int v=g[u][i];
        dfs(v);
        num[u] +=num[v];
        if(num[v] > num[prop]) prop=v;
    }
    if(num[prop]*2 >num[u]) {      //这里！！！如果下面的子树都不合法就枚举自己到祖先这一段的“子树”，也就是性质1。
        int now=ans[prop];
        while( (num[u]- num[now])*2 >num[u]){
            now =f[now];
        }
        ans[u] =now;
    }
}

//利用定义和性质1 ~~据说性质2也用到了然而并没有感觉~~

int main(void)
{
    memset(ans, 0, sizeof(ans));

    cin >>n >>q;
    for(int i=2; i<=n; i++) {
        scanf("%d", &f[i]);
        g[f[i]].push_back(i);
    }
    dfs(1);

    for(int i=1; i<=q; i++) {
        int a;
        scanf("%d", &a);
        printf("%d\n", ans[a]);
    }

    return 0;
}

dark法师以后回溯，利用重心定义和性质二自下向上回溯求
蛮神奇的
结束

树上差分：

专门开一篇不在这里讲

一道题

#include <bits/stdc++.h>

using namespace std;

int n,m,md=0;
vector<int> g[200003];
int dep[200003],maxd[200003],fa[200003];

void dfs(int u, int v, int d) {
    dep[v] =maxd[v] =d;
    fa[v] =u;
    for(int i=0; i<g[v].size(); i++) {
        int nxt=g[v][i];
        if(nxt !=u) {
            dfs(v, nxt, d+1);
            maxd[v] =max(maxd[v], maxd[nxt]);  //注意这里的处理 “每点能到达的最大深度”
            md =max(maxd[v], md);
        }
    }
    return;
}

int main(void)
{
    cin >>n >>m;
    for(int i=1; i<=n-1; i++) {
        int a,b;
        cin >>a >>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1,1,0);

    int ans=0,now=m;
    for(int i=0; i<=md; i++) {
        if(dep[now]>i) {           //判断爱力思有没有追上Boy
            ans =max(ans, maxd[now]*2);
        }
        now =fa[now];
    }

    cout <<ans<<endl;

    return 0; 
}

思路蛮好想，找到最deep(char(11)) dark的一条链，判断Boy是否能在被Alice赶上之前达到那条链，然后因为B走一步A走一步所以最大深度乘以2就好了。
dei码有些地方还是蛮神奇的于是码一手。

下一题

#include <bits/stdc++.h>

using namespace std;

int n,top=0;
vector<int> g[200003];
int du[200003],q[200003],dep[200003],vis[200003],fa[200003],color[200003];

void dfs(int org, int u) {
    int col=0;
    for(int i=0; i<g[u].size(); i++) {
        int v=g[u][i];

        if(v ==org || color[v]) continue;
        col++;
        while(col == color[org] || col ==color[u]) col++;

        color[v] =col;
        dfs(u, v);
    }

    return;
}

int main(void)
{
    memset(du, 0, sizeof(du));
    memset(color, 0, sizeof(color));

    cin >>n;
    for(int i=1; i<=n-1; i++) {
        int a,b;
        scanf("%d%d",&a ,&b);
        g[a].push_back(b);
        g[b].push_back(a);
        du[a]++;
        du[b]++;
    }
    int kind=0;
    for(int i=1; i<=n; i++) kind=max(kind, du[i]);
    cout <<kind+1<<endl;

    color[1] =1;
    dfs(0,1);

    for(int i=1; i<=n; i++) {
        cout <<color[i]<<" ";
    }
    cout <<endl;

    return 0;
}

下一题

大意就是在保证连通的情况下删除给定个数的节点，使剩下的点权和最大
因为点权为2的标号次方，所以保全标号尽可能大的节点是这辈子都不可能亏的，因为这个神奇的性质，此题要正向解，就是枚举尽可能大的点标vis，直至达到点数限制为止。
就酱
哎对了还要用到倍增找父亲，将父亲到自己这一段节点标vis

#include <bits/stdc++.h>

using namespace std;

int n,k;
vector<int> g[2000003];
int vis[1000003],dp[1000003][21],num[1000003],cnt[1000003],fa[1000003];

void dfs(int u, int v) {
    fa[v] =u;
    dp[v][0] =u;

    for(int i=1; i<=20; i++) {
        dp[v][i] =dp[dp[v][i-1]][i-1];    //倍增数组可以在dark法师内构造（码给自己看）
    }

    for(int i=0; i<g[v].size(); i++) {
        int nxt=g[v][i];
        if(nxt != u) {
            dfs(v, nxt);
        }
    }
}

int main(void)
{
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));

    cin >>n >>k;
    int cc=0;
    for(int i=1; i<=n-1; i++) {
        int a,b;
        scanf("%d%d", &a, &b);
        if(!cnt[a]) num[++cc] =a,cnt[a]=1;
        if(!cnt[b]) num[++cc] =b,cnt[b]=1;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(n, n);
    vis[n]=1;
    int res=n-k;

    for(int i=n-1; i>=1; i--) {
        if(vis[i]) continue;
        int l=1;
        int u=i;
        for(int j=20; j>=0; j--) {
            if(!vis[dp[u][j]]) {
                u =dp[u][j];
                l +=(1<<j);       //更新长度
            }
        }
        if(l <res) {
            res-=l;
            int f=i;
            while(l--) {          //记录跳的长度，不断找爸爸标vis
                vis[f]=1;
                f=fa[f];
            }
        }

        if(res ==0) break;
    }

    for(int i=1; i<=n; i++) {
        if(!vis[i]) printf("%d ", i);
    }

    return 0;
}