整理的演算法模板合集： ACM模板

一、樹的直徑

樹的直徑滿足如下性質：

若有多條直徑，則所有的直徑之間皆有公共點，
直徑的兩端一定是葉子，
樹中距離某一直徑端點最遠的點，至少有一個是該直徑的另一個端點，
對于樹上任意一個點，與之距離最遠的一個點，至少有一個直徑的端點，

給你一個無權無向的樹，撰寫程式以輸出該樹中最長路徑（從一個節點到另一個節點）的長度，在這種情況下，路徑的長度是我們從開始到目的地的遍歷邊數，

樹形DP

O ( n ) O(n) O(n)

const int N = 50007, M = 500007, INF = 0x3f3f3f3f;

int n, m, F[N], D[N], ans ;
int ver[N], nex[M], head[N], edge[N], tot;
bool vis[N];
void add(int x, int y, int z)
{
    ver[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot ++ ;
}

void dp(int x){
    vis[x] = 1;
    for(int i = head[x] ;~i; i =nex[i]){
        int y = ver[i], z = edge[i];
        if(vis[y])continue;
        dp(y);
        ans = max(ans, D[x] + D[y] + z);
        D[x] = max(D[x], D[y] + z);
    }
}

int main(){
    scanf("%d", &n);
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; ++ i){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y, 1), add(y, x, 1);
    }
    dp(1);
    printf("%d\n", ans);
    return 0;
}

兩次DFS / BFS（找到直徑的兩個端點）

O ( n ) O(n) O(n)

//兩次dfs一次求P一次求Q
void dfs(int u,int &ed){
    if(dis[u] > ans)ans = dis[u],ed = u;
    vis[u] = 1;
    for(int i = head[u];~i;i = nex[i]){
        int v = ver[i],w = edge[i];
        if(vis[v])continue;
        dis[v] = dis[u] + w;
        dfs(v,ed);
    }
    return ;
}
int p,q;
void solve(){
    dfs(1,p);
    ans = dis[p] = 0;
    memset(vis,0,sizeof vis);
    dfs(p,q);
    cout << ans << endl;
}

在一棵無根樹上，找 A , B , C A,B,C A,B,C三個點，使得 A B + B C ( A C > B C ) AB+BC(AC>BC) AB+BC(AC>BC)或 A C + A B ( B C > A C ) AC+AB(BC>AC) AC+AB(BC>AC)最大，

我們假設 A C > B C AC>BC AC>BC，那么答案就是找到最大 A B + B C AB+BC AB+BC簡單貪心一下，先令AB最大，然后再找一個相應的最大的BC，強調要滿足(AC>AB)所以我們首先找出樹的直徑，然后列舉除了兩個端點外的點 C C C，使得 m i n ( A C , B C ) min(AC,BC) min(AC,BC)最大，答案就是樹的直徑 + m i n ( A C , B C ) +min(AC,BC) +min(AC,BC)

typedef long long ll;
const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;

int n, m;
ll d[N], copy_d[N];
bool vis[N];
int head[N], ver[M], nex[M], edge[M], tot;

void add(int x, int y, int z)
{
    ver[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot ++ ;
}

int bfs(int S)
{
    queue<int>q;
    memset(d, 0, sizeof d);
    memset(vis, 0, sizeof vis);
    //while(q.size())q.pop();
    q.push(S), vis[S] = 1;

    int maxx = 0, maxid;
    while(q.size()){
        int x = q.front();
        q.pop();
        for(int i = head[x]; ~i; i = nex[i]){
            int y = ver[i], z = edge[i];
            if(vis[y])continue;
            vis[y] = 1;
            d[y] = d[x] + z;
            q.push(y);
            if(d[y] > maxx){
                maxx = d[y];
                maxid = y;
            }
        }
    }
    return maxid;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof head);
    for(int i = 1; i <= m; ++ i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    int p, q;
    p = bfs(1);
    q = bfs(p);
    ll ans = d[q];//the length of AB
    for(int i = 1; i <= n; ++ i){
        copy_d[i] = d[i];
    }
    bfs(q);
    ll res = 0;
    for(int i = 1; i <= n; ++ i){
        res = max(res, min(d[i], copy_d[i]));//find the longest edges among the remaining edges
    }
    ans += res;
    printf("%lld\n", ans);
    return 0;
}

二、動態修改樹的邊權并求每個時刻的直徑（線段樹）

有一個n個點的帶權無向樹，q次操作，每次修改一條邊的權值，要求在每次修改后，輸出樹的直徑大小，強制在線，

/*lmx,rmx,lmi,rmi,ld,rd,lrd,ans前綴/后綴的最大/最小和，前綴右減左最大，
后綴右減左最大，兩端點必須選滿右減左最大，任意子串右減左最大*/
#include<bits/stdc++.h>
#define ls(a) ((a)<<1)
#define rs(a) ((a)<<1|1)
#define N 200001
#define int long long
using namespace std;
typedef long long ll;
#define G if(++ip==ie)if(fread(ip=ibuf,1,LL,stdin))
const int LL=1<<19;
char ibuf[LL],*ie=ibuf+LL,*ip=ie-1;
inline char nc(void){G;return *ip;}
//#define getchar nc
inline ll read(void){
	char opt;ll flag=1,res=0;
	while((opt=getchar())<'0'||opt>'9')if(opt=='-')flag=-1;
	while(opt>='0'&&opt<='9'){res=(res<<3)+(res<<1)+opt-'0';opt=getchar();}
	return res*flag;
}
int n,m,st[N],top,q;
struct edge{int to;ll v;int x;};vector<edge>g[N];
ll w,sum[N<<2],lmx[N<<2],rmx[N<<2],lmi[N<<2],rmi[N<<2],ld[N<<2],rd[N<<2],lrd[N<<2],ans[N<<2],lastans,p[N][2];
void pushup(int x){
	sum[x]=sum[ls(x)]+sum[rs(x)]; 
	lmx[x]=max(lmx[ls(x)],sum[ls(x)]+lmx[rs(x)]); 
	rmx[x]=max(rmx[rs(x)],sum[rs(x)]+rmx[ls(x)]);
	lmi[x]=min(lmi[ls(x)],sum[ls(x)]+lmi[rs(x)]);
	rmi[x]=min(rmi[rs(x)],sum[rs(x)]+rmi[ls(x)]);
	ld[x]=max(ld[ls(x)],max(ld[rs(x)]-sum[ls(x)],lrd[ls(x)]+lmx[rs(x)])); 
	rd[x]=max(rd[rs(x)],max(sum[rs(x)]+rd[ls(x)],lrd[rs(x)]-rmi[ls(x)]));
	lrd[x]=max(lrd[ls(x)]+sum[rs(x)],lrd[rs(x)]-sum[ls(x)]);
	ans[x]=max(max(ans[ls(x)],ans[rs(x)]),max(ld[rs(x)]-rmi[ls(x)],rd[ls(x)]+lmx[rs(x)])); 
}
inline void Build(int pos,int l,int r){
	ll v;if(l==r)return sum[pos]=(v=st[l]),lmx[pos]=rmx[pos]=max(v,0ll),lmi[pos]=rmi[pos]=min(v,0ll),ld[pos]=rd[pos]=lrd[pos]=ans[pos]=v,void();
	int mid=(l+r)>>1;
	Build(ls(pos),l,mid),Build(rs(pos),mid+1,r);
	pushup(pos);
}
inline void Change(int pos,int l,int r,int x,ll v){
	if(l==r)return sum[pos]=v,lmx[pos]=rmx[pos]=max(v,0ll),lmi[pos]=rmi[pos]=min(v,0ll),ld[pos]=rd[pos]=lrd[pos]=ans[pos]=v,void();
	int mid=(l+r)>>1;
	(x<=mid)?Change(ls(pos),l,mid,x,v):Change(rs(pos),mid+1,r,x,v);
	pushup(pos);
}
inline void dfs(int x,int prt){
	int y;for(auto t:g[x])if((y=t.to)^prt)st[*p[t.x]=++top]=t.v,dfs(y,x),st[p[t.x][1]=++top]=-t.v;
}
signed main(void){
	int i,x;ll y,z;n=read(),q=read(),w=read();
	for(i=1;i<n;++i)x=read(),y=read(),z=read(),g[x].push_back({y,z,i}),g[y].push_back({x,z,i});
	dfs(1,0);Build(1,1,top);
	while(q--){
		x=(read()+lastans)%(n-1)+1,y=(read()+lastans)%w;
		Change(1,1,top,*p[x],y),Change(1,1,top,p[x][1],-y);
		printf("%lld\n",lastans=ans[1]);
	}
    return 0;
}

三、樹的重心

重心的性質

以樹的重心為根時，所有子樹的大小都不超過整棵樹大小的一半，
把兩棵樹通過一條邊相連得到一棵新的樹，那么新的樹的重心在連接原來兩棵樹的重心的路徑上，
在一棵樹上添加或洗掉一個葉子，那么它的重心最多只移動一條邊的距離，
樹中所有點到某個點的距離和中，到重心的距離和是最小的；如果有兩個重心，那么到它們的距離和一樣，
一棵樹最多有兩個重心，且相鄰，

給定一棵樹,求樹的重心的編號以及重心洗掉后得到的最大子樹的節點個數size,如果size相同就選取編號最小的.

const int N = 50007, M = 500007, INF = 0x3f3f3f3f;
typedef long long ll;

int n, m;
int head[N], ver[M], nex[M], tot;
ll T;
int son[N], ans, pos;
bool vis[N];

void add(int x, int y)
{
    ver[tot] = y;
    nex[tot] = head[x];
    head[x] = tot ++ ;
}

void dfs(int x)
{
    vis[x] = 1, son[x] = 1;
    int res = 0;
    for(int i = head[x]; ~i; i = nex[i]){
        int y = ver[i];
        if(!vis[y]){
            dfs(y);
            son[x] += son[y];
            res = max(res, son[y]);//x下面的子樹
        }
    }
    res = max(res, n - son[x]);//x上面的子樹
    if(res < ans || (res == ans && x < pos)){
        ans = res, pos = x;
    }
}

int main()
{
    scanf("%lld", &T);
    while(T -- ){
        tot = 0;
        memset(head, -1, sizeof head);
        memset(vis, 0, sizeof vis);
        ans = INF;

        scanf("%d", &n);
        for(int i = 1; i < n; ++ i){
            int x, y;
            scanf("%d%d", &x, &y);
            add(x, y), add(y, x);
        }
        dfs(1);
        printf("%d %d\n", pos, ans);
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/46657.html

標籤：其他

上一篇：2020.09.13 組隊訓練賽問題 F: Game of Gnomes

下一篇：領扣LintCode演算法問題答案-322. 象棋游戲

模板 - 樹上問題（樹的直徑、動態查詢樹的直徑、樹的重心）

目錄

一、樹的直徑

樹形DP

兩次DFS / BFS（找到直徑的兩個端點）

二、動態修改樹的邊權并求每個時刻的直徑（線段樹）

三、樹的重心