每日一题 3.31 城市网络

这题一看 图论题 不会…… 那咋办呢 只能慢慢看 慢慢学
然后发现这题好像是使用了倍增数组的相关知识（这个还是有点熟的 学lca的时候弄了半天）
这题的关键就是那句 保证 v 在 u 前往首都的最短路径上 （v一定是u的祖先）
于是那个熟悉的方程就出来了 f[i][j]=f[f[i][j-1]][j-1]
这题具体实现如下（附备注）
输出方式还是坑了我一次（傻傻的输出的空格.....）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int const N = 2e5 + 5;
int n,q,val[N],m[N],ans;///val表示价值 m记录祖先
vector<int> g[N];///二维动态数组存边
int f[N][20], de[N];
/// f[i][j]表示 从i到目标点买了2^j次物品  所以有 f[i][j]=f[f[i][j-1]][j-1]
void dfs(int u, int p)///倍增常规操作
{
    de[u] = de[p] + 1;
    if (val[u] < val[p])
    {
        f[u][0] = p;
    }
    else
    {
        int x = p;
        for (int i = 19; i >= 0; --i)///x逼近第一个比val[u]大的结点下方的结点
        {
            if (f[x][i] && val[u] >= val[f[x][i]])
            {
                x = f[x][i];
            }
        }
        f[u][0] = f[x][0];///得到第一个比val[u]大的的祖先结点
    }
    for (int i = 1; i <= 19; ++i)///递推
    {
        f[u][i] = f[f[u][i-1]][i-1];
    }
    for (int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i];
        if (v == p) continue;///到目标节点
        dfs(v, u);
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for (int i = 1; i <= n; ++i) scanf("%d",&val[i]);
    for (int i = 0; i < n-1; ++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);///连边
        g[v].push_back(u);
    }
    for (int i = 1; i <= q; ++i)
    {
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);///题目保证了v是u的祖先
        g[n+i].push_back(u);///加点
        g[u].push_back(n+i);
        val[n+i] = c, m[i] = v;///新结点val设为c，记录目标祖先v
    }
    dfs(1, 0);
    for (int i = 1; i <= q; ++i)
    {
        int u,v;
        u = n+i, v = m[i],ans=0;
        for (int i = 19; i >= 0; --i)
        {
            if (de[f[u][i]] >= de[v])///u向v跳
            {
                u = f[u][i];
                ans += (1<<i);///买了2^i次
            }
        }
       printf("%d\n",ans);
    }
    return 0;
}