hdu 7136 Jumping Monkey

分析：

• 并查集+重构树

• 可以想到 B F S BFS BFS 去遍历，每次从当前权值最大点出发跑一遍 B F S BFS BFS，经过的点的 d e p + + dep++ dep++

  然后，便将权值最大点去掉，继续重复上一个操作

  但是，这样显然会 T T T（代码见下文）

• 考虑如何优化？（从比赛开始到结束，也没想出怎么优化）

  n n n 遍 B F S BFS BFS ，过程有很多步是重复的

  如果这棵树以权值最大点为根，从上到下的权值是递减的，那答案就是每个节点的深度（这就很 n i c e nice nice ）

• 如何重构这棵树？

  考虑普遍情况和上述的特殊情况，区别在哪？

  区别就在于：普遍情况并非严格递减的

  要有一种重构的方法，将这棵树变成特殊情况的，且还不会影响最终答案

• 重构方法

  按点权从小到大枚举结点 u u u ，并将 u u u 作为所有与 u u u 相连的（已经枚举过的）连通块的根（这里要用并查集维护）

  从而建立一棵新树，每个结点的深度（根的深度为 1 1 1 ）即是答案。

  重构方法的正确性，多画几张图就能理解了~

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
	return f*x;
}
struct Node
{
    int next,to;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v)
{
    e[++tot].next=head[u];
    e[tot].to=v;
    head[u]=tot;
}
struct graph
{
    int w,id;
    bool operator <(const graph &a) const { return w<a.w; }
}b[N];
int f[N];
int fd(int k) { return f[k]==k ? k : f[k]=fd(f[k]); }
vector <int> g[N];
int dep[N];
void dfs(int u)
{
    for(auto v : g[u])
    {
        dep[v]=dep[u]+1;
        dfs(v);
    }
}
int vis[N];
signed main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        n=read();
        tot=0;
        for(int i=1;i<=n;i++) 
        { 
            f[i]=i; g[i].clear(); dep[i]=vis[i]=head[i]=0;
        }
        for(int i=1;i<n;i++)
        {
            int u,v;
            u=read(); v=read();
            add(u,v);
            add(v,u);
        }
        for(int i=1;i<=n;i++)
        {
            b[i].w=read();
            b[i].id=i;
        }
        sort(b+1,b+1+n);
        vis[b[1].id]=1;
        for(int i=2;i<=n;i++)
        {
            int u=b[i].id;
            for(int i=head[u]; i ;i=e[i].next)
            {
                int v=e[i].to;
                if(vis[v])
                {
                    int y=fd(v); // 找到连通块的祖宗
                    f[y]=u;
                    g[u].push_back(y); // 重构树
                }
            }
            vis[u]=1; //要维护的集合里加入该点
        }
        dep[b[n].id]=1;
        dfs(b[n].id);
        for(int i=1;i<=n;i++) printf("%d\n",dep[i]);       
    }
    return 0;
}

BFS (T了的)

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
	return f*x;
}
struct Node
{
    int next,to;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v)
{
    e[++tot].next=head[u];
    e[tot].to=v;
    head[u]=tot;
}
struct graph
{
    int w,id;
    bool operator <(const graph &a) const { return w>a.w; }
}b[N];
int dep[N];
int vis[N],vis1[N];
signed main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        n=read();
        tot=0;
        for(int i=1;i<=n;i++) 
        { 
            dep[i]=vis[i]=head[i]=0;
        }
        for(int i=1;i<n;i++)
        {
            int u,v;
            u=read(); v=read();
            add(u,v);
            add(v,u);
        }
        for(int i=1;i<=n;i++)
        {
            b[i].w=read();
            b[i].id=i;
        }
        sort(b+1,b+1+n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++) vis1[j]=0;
            queue <int> q;
            q.push(b[i].id);
            dep[b[i].id]+=1;
            vis[b[i].id]=1; // 去掉当前点
            vis1[b[i].id]=1;
            while(!q.empty())
            {
                int u=q.front();
                q.pop();
                for(int j=head[u]; j ;j=e[j].next)
                {
                    int v=e[j].to;
                    if(vis[v] || vis1[v]) continue;
                    dep[v]+=1;
                    q.push(v);
                    vis1[v]=1;
                }
            }
        }
        for(int i=1;i<=n;i++) printf("%d\n",dep[i]); 
    }
    return 0;
}