首页 > 其他分享 >Race dsu on tree写法

Race dsu on tree写法

时间:2023-01-06 14:12:29浏览次数:47  
标签:son int dsu tree ++ next dep Race now

//跑不过,不知道为啥,感觉逻辑都很正确了

//题意:给出一棵带边权的树,询问一条权值为k的路径经过点的最小值是多少

//思路:因为涉及到最小值问题,所以树性dp好像不行(其实暂时不清楚,因为dp没怎么碰过)
//      然后这种路径可合并问题很明显是可以用dsu on tree做的 因为没有树上修改的步骤
//


/*# include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
struct edge {
    int to, w;
    edge(int a = 0, int b = 0) {
        to = a, w = b;
    }
};
int n, k, ans = 1e9;
vector<edge> mp[N];
int dep[N], dep1[N], f[N], sz[N], son[N], id[N], nid[N], cnt;
map<int, int> depp;//用于记录已经出现的路径长度,因为我们要求的是最小深度,所以我们哈希值为 最小深度
void dfs(int x, int fa) {
    sz[x] = 1;
    f[x] = fa;
    id[x] = ++cnt;
    nid[cnt] = x;
    for (auto y : mp[x]) {
        if (y.to == fa) continue;
        dep[y.to] += 1;
        dep1[y.to] += y.w;
        dfs(y.to, x);
        sz[x] += sz[y.to];
        if (sz[son[x]] < sz[y.to]) son[x] = y.to;
    }
}
void add(int x, int k) {
    int dp = dep1[x];
    if (k == 1) {
        if (depp[dp] == 0||depp.find(dp)==depp.end())  depp[dp] = dep[x];
        else depp[dp] = min(depp[dp], dep[x]);
    }
    else {
        depp[dp] = 0;
    }
}
void dfs1(int x, bool keep) {
    for (auto y : mp[x]) {
        if (y.to == son[x] || y.to == f[x]) continue;
        dfs1(x, 0);
    }
    if (son[x]) dfs1(son[x], 1);

    //用dfs序代替遍历来赋值,优化常数

    //add(x, 1);
    for (auto y : mp[x]) {
        if (y.to == son[x] || y.to == f[x]) continue;
        for (int i = 0; i < sz[y.to]; i++) {
            int nxt = nid[id[y.to] + i];
            int dpt = k - dep1[nxt] + 2 * dep1[x];
            if (depp[dpt]) ans = min(ans, dep[nxt] + depp[dpt] - 2 * dep[x]);
        }
        //一个子树做完,再加入这个子树,保证不重复计算贡献

        for (int i = 0; i < sz[y.to]; i++)
            add(nid[id[y.to] + i], 1);
    }
    
    if (!keep)
        for (int i = 0; i < sz[x]; i++)
            add(nid[id[x] + i], -1);
}
signed main(){
    cin >> n >> k;
    memset(son, sizeof(son), 0);
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c; cin >> a >> b >> c;
        a++; b++;
        mp[a].push_back({ b,c });
        mp[b].push_back({ a,c });
    }
    dfs(1, 0);
    dfs1(1, 0);
    if (ans == 1e9) cout << -1;
    else cout << ans;
    return 0;
}
*/

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

int n, k;
vector <int>to[200005];
vector <int>len[200005];
long long deep[200005];
int diep[200005];
int siz[200005];
int son[200005];
int nid[200005];
int id[200005];
int cnt;

map< long long, int >dep;
int ans = 1e9;

void dfs1(int now, int last) {
    siz[now] = 1;
    id[now] = ++cnt;
    nid[cnt] = now;
    int mx = 0;
    for (int i = 0; i < to[now].size(); i++) {
        int next = to[now][i];
        if (next == last)continue;
        deep[next] = deep[now] + len[now][i];
        diep[next] = diep[now] + 1;
        dfs1(next, now);
        siz[now] += siz[next];
        if (siz[next] > mx) {
            mx = siz[next];
            son[now] = next;
        }
    }
}

void updata(int x, int k) {
    int dx = deep[x];
    if (k == -1) {
        dep[dx] = 0;
    }
    else {
        int tmp = dep[dx];
        if (tmp == 0)tmp = 1e9;
        dep[dx] = min(tmp, diep[x]);
    }
}

void dfs2(int now, int last, bool keep) {
    for (auto next : to[now]) {
        if (next == son[now] or next == last)continue;
        dfs2(next, now, 0);
    }
    if (son[now])dfs2(son[now], now, 1);
    for (auto next : to[now]) {
        if (next == son[now] or next == last)continue;
        for (int i = 0; i < siz[next]; i++) {
            int nxt = nid[id[next] + i];
            int req = k + 2 * deep[now] - deep[nxt];
            if (dep[req]) {
                ans = min(ans, dep[req] + diep[nxt] - 2 * diep[now]);
            }
        }
        for (int i = 0; i < siz[next]; i++) {
            updata(nid[id[next] + i], 1);
        }
    }
    updata(now, 1);
    if (dep[deep[now] + k])ans = min(ans, dep[deep[now] + k] - diep[now]);
    if (keep == 0) {
        for (int i = 0; i < siz[now]; i++) {
            updata(nid[id[now] + i], -1);
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        to[u].push_back(v);
        to[v].push_back(u);
        len[u].push_back(w);
        len[v].push_back(w);
    }
    diep[0] = 1;
    dfs1(0, 0); dfs2(0, 0, 0);
    if (ans == 1e9)ans = -1;
    cout << ans;
    return 0;
}

 

标签:son,int,dsu,tree,++,next,dep,Race,now
From: https://www.cnblogs.com/Aacaod/p/17030253.html

相关文章

  • 【Python】traceback使用
    traceback使用importtracebackimportosfrompathlibimportPathfromioimportStringIOfp=StringIO()#使用内存try:print('---------')int('abc......
  • 单细胞 | CNV和SNV(genome + MT)推测lineage tree
     正式进入cancergenomics领域,只不过是从scRNA-seq与scATAC-seq入手。我们的问题是如何从有限的SNV和CNV数据里推测出CRC的lineage的关系。 使用的工具:https://git......
  • C#(Java)将List集合构建成Tree树
    C#(Java)将List集合构建成Tree树子安树构建算法,可以通过空间换时间进一步优化速度树结构的类publicclassMyTreeNode{publicMyTreeNode(long?iD,long?pare......
  • NERDtree 快捷键
    NERDtree操作指令ctrl+w+h光标focus左侧树形目录ctrl+w+l光标focus右侧文件显示窗口ctrl+w+w光标自动在左右侧窗口切换ctrl+w+r......
  • C#实现treeview节点上下左右自由移动
    以下是节点移动类NodeMove.cs源码:usingSystem;usingSystem.Collections.Generic;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Collections;namespaceNo......
  • C#实现TreeView向XML的绝对转换类
    从第一次接触XML开始就想写一个能实现tree和XML灵活转换的类了。写这个类大概用去了将近半天的时间,花的时间有些长了。呵呵。。好在收获颇多,熟练了XML的读写类,对C#中的forea......
  • ExtJS-UI组件-TreePanel
    ExtJS教程汇总:https://www.cnblogs.com/cqpanda/p/16328016.html转载请注明出处:https://www.cnblogs.com/cqpanda/p/16587500.html更新记录2023年1月2日从笔记迁移到......
  • element ui --el-select 嵌套el-tree多选联动、删除联动
    需求:el-select下拉框嵌套el-tree树形组件完成多选、删除、搜索、清空选项等联动功能。特殊需求:(当子节点全部选中时el-select中只展示父节点tag,el-tree组件父子节点全......
  • 关于sourcetree 代码库更改用户密码后报fatal:Authentication failed for 的问题
      解决方案:**重置sourceTree密码:**找到sourceTree的安装目录将C:\Users\USERNAME\AppData\Local\Atlassian\SourceTree并删除passwd文件(记得把sourceTree关......
  • 关于sourcetree新建远端分支后本地没有同步更新的问题
    点击右上角的命令行模式  输入:gitremoteupdateorigin--prune并回车   回到Sourcetree,可以看到远程分支多了一个,如果没有就刷新一下Sourcetree 原贴:(4......