• 树上启发式合并

    强大的解决对于子树的询问问题。

    有个英文名字叫 dsu on tree。

    一种是基于重链剖分的,一种是基于set map的启发式合并的。

    第一种就是先走轻边,再走重边,重边的不改回来,这样修改次数就是 $logn$ 次的。

    第二种就是看set map的size,把size小的并到大的上。

     

    600E - Lomsat gelral

    模板题啦

    分享图片
    #include <bits/stdc++.h>
    #define ll long long
    
    const int N = 1e5 + 7;
    
    int n, cc[N], col[N], son[N], sz[N], skip[N];
    ll ans[N];
    std::vector<int> G[N];
    
    void dfs1(int u, int fa = 0) {
        sz[u] = 1;
        for (auto v: G[u]) {
            if (v == fa) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) son[u] = v;
        }
    }
    
    ll sum;
    int cx;
    
    void edt(int u, int fa, int k) {
        cc[col[u]] += k;
        if (k > 0 && cc[col[u]] >= cx) {
            if (cc[col[u]] > cx) 
                sum = 0, cx = cc[col[u]];
            sum += col[u];
        }
        for (auto v: G[u])
            if (v != fa && !skip[v])
                edt(v, u, k);
    }
    
    void dfs(int u, int fa = 0, bool kep = 0) {
        for (auto v: G[u]) 
            if (v != fa && v != son[u])
                dfs(v, u);
        if (son[u])
            dfs(son[u], u, 1), skip[son[u]] = 1;
        edt(u, fa, 1);
        ans[u] = sum;
        if (son[u])
            skip[son[u]] = 0;
        if (!kep)
            edt(u, fa, -1), cx = sum = 0;
    }
    
    int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) 
            scanf("%d", col + i);
        for (int i = 1, u, v; i < n; i++) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs1(1);
        dfs(1);
        for (int i = 1; i <= n; i++)
            printf("%lld%c", ans[i], " \n"[i == n]);
        return 0;
    }
    View Code

     

    570D - Tree Requests

    把询问离线,一些字母能组成回文串,即出现偶数次的字母不能超过一个,那么对每一个深度用一个26位的二进制数表示一个字母出现的奇偶性,记为 $cnt[dep]$ 即可。

    分享图片
    #include <bits/stdc++.h>
    #define pii pair<int, int>
    #define fi first
    #define se second
    
    const int N =  5e5 + 7;
    std::vector<int> G[N];
    std::vector<std::pii> que[N];
    int cnt[N], n, m, dep[N], sz[N], son[N];
    char s[N];
    bool ans[N], skip[N];
    
    void dfs1(int u, int d) {
        dep[u] = d;
        sz[u] = 1;
        for (auto v: G[u]) {
            dfs1(v, d + 1);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) son[u] = v;
        }
    }
    
    void edt(int u) {
        cnt[dep[u]] ^= (1 << (s[u] - a));
        for (auto v: G[u]) 
            if (!skip[v]) edt(v);
    }
    
    bool check(int d) {
        int res = 0;
        for (int i = 0; i < 26; i++)
            if (cnt[d] >> i & 1)
                res++;
        return res <= 1;
    }
    
    void dfs(int u, int keep = 0) {
        for (auto v: G[u])
            if (v != son[u]) dfs(v, 0);
        if (son[u])
            dfs(son[u], 1), skip[son[u]] = 1;
        edt(u);
        for (auto p: que[u])
            ans[p.se] = check(p.fi);
        if (son[u]) skip[son[u]] = 0;
        if (!keep)
            edt(u);
    }
    
    int main() {
    //    freopen("in.txt", "r", stdin);
        scanf("%d%d", &n, &m);
        for (int i = 2; i <= n; i++) {
            int x;
            scanf("%d", &x);
            G[x].push_back(i);
        }
        scanf("%s", s + 1);
        for (int i = 1, u, h; i <= m; i++) {
            scanf("%d%d", &u, &h);
            que[u].push_back(std::pii(h, i));
        }
        dfs1(1, 1);
        dfs(1);
        for (int i = 1; i <= m; i++)
            puts(ans[i] ? "Yes" : "No");
        return 0;
    }
    View Code

     

    Sgu507

    想用重链剖分的写法。用一个multiset维护出现的数字,一个multiset维护每个插入的数和附近两个数的差值.

    但是这跟插入顺序有关,插入的时候正着插入,删除的时候倒着删除,然后WA on 20了... 正着删除有RE on 20了...

    看了一下别人的解法就是,每个结点维护一个set,发现这个set元素个数最多是所有叶子个数,空间能接受,然后就启发式合并就OK了。

    分享图片
    #include <bits/stdc++.h>
    
    namespace IO {
        void read() {}
        template <typename T, typename... T2>
        inline void read(T &x, T2 &... oth) {
            T f = 1; x = 0;
            char ch = getchar();
            while (!isdigit(ch)) { if (ch == -) f = -1; ch = getchar(); }
            while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
            x *= f;
            read(oth...);
        }
    } // using namespace IO
    #define read IO::read
    #define print IO::print
    #define flush IO::flush
    
    const int N = 1e5 + 7;
    const int INF = 2147483647;
    std::vector<int> vec[N];
    std::set<int> st[N];
    int n, m, color[N], ans[N];
    
    int merge(int u, int v) {
        if (st[u].size() < st[v].size())
            std::swap(st[u], st[v]);
        int res = INF;
        for (std::set<int>::iterator it = st[v].begin(); it != st[v].end(); it++) {
            auto i = st[u].lower_bound(*it);
            if (i == st[u].begin()) {
                res = std::min(res, *i - *it);
            } else if (i == st[u].end()) {
                i--;
                res = std::min(res, *it - *i);
            } else {
                res = std::min(res, *i - *it);
                i--;
                res = std::min(res, *it - *i);
            }
            st[u].insert(*it);
        }
        st[v].clear();
        return res;
    }
    
    void dfs(int u) {
        ans[u] = INF;
        if (vec[u].size() == 0) {
            st[u].insert(color[u]);
            return;
        }
        for (int v: vec[u]) {
            dfs(v);
            ans[u] = std::min(ans[u], ans[v]);
            ans[u] = std::min(ans[u], merge(u, v));
        }
    }
    
    int main() {
        read(n, m);
        for (int i = 2; i <= n; i++) {
            int u;
            read(u);
            vec[u].push_back(i);
        }
        for (int i = n - m + 1; i <= n; i++)
            read(color[i]);
        dfs(1);
        for (int i = 1; i <= n - m; i++)
            printf("%d%c", ans[i], " \n"[i == n - m]);
        return 0;
    }
    View Code

     

    HackerEarth, The Grass Type

    这个就是每个结点维护一个map表示其子树钟出现过的数字以及出现的次数。

    然后根据合并前枚举小的map里面的每个元素,看看大的map中能与其相乘成为当前结点的值的就行了。

    分享图片
    #include <bits/stdc++.h>
    #define ll long long
    
    const int N = 1e5 + 7;
    std::map<int, int> mp[N];
    int n, val[N];
    std::vector<int> vec[N];
    ll ans;
    
    void merge(int u, int v) {
        if (mp[u].size() < mp[v].size()) std::swap(mp[u], mp[v]);
        for (auto p: mp[v]) {
            if (val[u] % p.first == 0)
                ans += 1LL * p.second * mp[u][val[u] / p.first];
        }
        for (auto p: mp[v]) 
            mp[u][p.first] += p.second;
        mp[v].clear();
    }
    
    void dfs(int u, int fa) {
        mp[u][val[u]] = 1;
        for (int v: vec[u]) {
            if (v == fa) continue;
            dfs(v, u);
            merge(u, v);
        }
    }
    
    int main() {
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        for (int i = 1; i <= n; i++)
            scanf("%d", val + i);
        dfs(1, 0);
        printf("%lld\n", ans);
        return 0;
    }
    View Code

     

    246E - Blood Cousins Return

    对每一个深度用一个map维护出现的字符串以及出现的次数,然后然后就做完了。

    分享图片
    #include <bits/stdc++.h>
    #define pii pair<int, int>
    #define fi first
    #define se second
    
    const int N = 1e5 + 7;
    char s[N][22];
    std::vector<int> vec[N];
    std::vector<std::pii> query[N];
    std::map<std::string, int> mp[N];
    int n, son[N], sz[N], dep[N], ans[N], root, cnt[N];
    bool skip[N];
    
    void dfs1(int u, int d) {
        sz[u] = 1;
        dep[u] = d;
        son[u] = -1;
        for (int v: vec[u]) {
            dfs1(v, d + 1);
            sz[u] += sz[v];
            if (son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
        }
    }
    
    void edt(int u, int k) {
        mp[dep[u]][s[u]] += k;
        int w = mp[dep[u]][s[u]];
        if (k == 1 && w == 1) cnt[dep[u]]++;
        if (k == -1 && w == 0) cnt[dep[u]]--;
        assert(cnt[dep[u]] >= 0);
        for (int v: vec[u])
            if (!skip[v])
                edt(v, k);
    }
    
    void dfs(int u, bool keep = 0) {
        for (int v: vec[u])
            if (v != son[u])
                dfs(v);
        if (son[u] != -1)
            dfs(son[u], 1), skip[son[u]] = 1;
        edt(u, 1);
        for (auto p: query[u]) 
            ans[p.se] = cnt[dep[u] + p.fi];
        if (son[u] != -1)
            skip[son[u]] = 0;
        if (!keep)
            edt(u, -1);
    }
    
    int main() {
        scanf("%d", &n);
        for (int i = 1, u; i <= n; i++) {
            scanf("%s%d", s[i], &u);
            vec[u].push_back(i);
        }
        int m;
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
            int u, k;
            scanf("%d%d", &u, &k);
            query[u].push_back(std::pii(k, i));
        }
        dfs1(0, 0);
        dfs(0, 1);
        for (int i = 1; i <= m; i++)
            printf("%d\n", ans[i]);
        return 0;
    }
    View Code

     

    208E - Blood Cousins

    先转换一下询问,把 $v_i$ 往上跳 $p_i$ 步得到 $u_i$,变成询问 $u_i$ 有多少个 $p_i$ 级儿子。然后就做完了。

    分享图片
    #include <bits/stdc++.h>
    #define pii pair<int, int>
    #define fi first
    #define se second
    
    const int N = 1e5 + 7;
    int dep[N], son[N], sz[N], n, fa[N][20], ans[N];
    bool skip[N];
    std::vector<int> vec[N];
    std::vector<std::pii> query[N];
    
    void dfs1(int u, int pre = 0, int d = 0) {
        dep[u] = d;
        fa[u][0] = pre;
        for (int i = 1; i <= 18; i++) {
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
            if (!fa[u][i]) break;
        }
        sz[u] = 1;
        son[u] = -1;
        for (int v: vec[u]) {
            dfs1(v, u, d + 1);
            sz[u] += sz[v];
            if (son[u] == -1 || sz[son[u]] < sz[v])
                son[u] = v;
        }
    }
    
    int jump(int u, int k) {
        for (int i = 18; ~i; i--)
            if (k >> i & 1)
                u = fa[u][i];
        return u;
    }
    
    int cnt[N];
    
    void edt(int u, int k) {
        cnt[dep[u]] += k;
        for (int v: vec[u])
            if (!skip[v])
                edt(v, k);
    }
    
    void dfs(int u, bool keep = 0) {
        for (int v: vec[u])
            if (v != son[u])
                dfs(v);
        if (son[u] != -1) 
            dfs(son[u], 1), skip[son[u]] = 1;
        edt(u, 1);
        for (auto p: query[u]) {
            ans[p.se] = cnt[dep[u] + p.fi] - 1;
        }
        if (son[u] != -1)
            skip[son[u]] = 0;
        if (!keep)
            edt(u, -1);
    }
    
    int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int u;
            scanf("%d", &u);
            vec[u].push_back(i);
        }
        int m;
        scanf("%d", &m);
        dfs1(0);
        for (int i = 1; i <= m; i++) {
            int u, k;
            scanf("%d%d", &u, &k);
            u = jump(u, k);
            if (u) query[u].push_back(std::pii(k, i));
        }
        dfs(0, 1);
        for (int i = 1; i <= m; i++)
            printf("%d%c", ans[i], " \n"[i == m]);
        return 0;
    }
    View Code

     

    待续...

    相关文章
    相关标签/搜索
    90885公牛网站彩霸王白小姐一肖中特马2020马会免费资料大全白小姐中特网400500好彩堂中特网三肖中特期期准黄大仙 浮山县| 若羌县| 彰化市| 中超| 呈贡县| 湖口县| 县级市| 长治县| 磐安县| 新宁县| 桃江县| 姚安县| 工布江达县| 新宾| 河津市| 房山区| 夏邑县| 昌江| 青神县| 潮州市| 平南县| 若尔盖县| 宁波市| 呼和浩特市| 四川省| 沂源县| 武清区| 岚皋县| 高平市| 新宁县| 宁蒗| 龙川县| 定襄县| 长沙市| 宁明县| 策勒县| 本溪| 永和县| 托克逊县| 多伦县| 城步| 鞍山市| 左贡县| 商水县| 曲水县| 九江市| 正镶白旗| 游戏| 隆安县| 平顺县| 特克斯县| 康保县| 本溪市| 前郭尔| 遵义县| 安溪县| 运城市| 咸阳市| 莱西市| 拉萨市| 无为县| 安仁县| 屯留县| 长乐市| 桂林市| 玛沁县| 绥德县| 都江堰市| 页游| 长治市| 锡林郭勒盟| 香港| 北票市| 海安县| 鹿泉市| 呈贡县| 三都| 宜君县| 宜宾市| 青神县| 新田县| 宁远县| 庆元县| 通化市| 伊宁县| 汽车| 汶上县| 凤翔县| 彰武县| 额敏县| 侯马市| 仁寿县| 龙胜| 华容县| 汉寿县| 徐闻县| 龙州县| 吕梁市| 芮城县| 措美县| 恩施市| 东辽县| 南充市| 上林县| 容城县| 石台县| 南投县| 高安市| 蕉岭县| 尼木县| 南召县| 临邑县| 调兵山市| 古蔺县| 兴文县| 乐清市| 衡水市| 汝州市| 宣武区| 浦北县| 花莲县| 台北市| 龙口市| 黄梅县| 凤庆县| 台南县| 织金县| 广东省| 四子王旗| 咸宁市| 鹤岗市| 波密县| 安庆市| 沐川县| 保亭| 黎平县| 岐山县| 新乐市| 教育| 于田县| 繁峙县| 梅河口市| 嘉荫县| 库车县| 凤冈县| 桓台县| 唐海县| 巴青县| 绥中县| 汉川市| 潞城市| 明溪县| 湟源县| 赣榆县| 临澧县| 资兴市| 墨脱县| 肥西县| 金山区| 广东省| 淅川县| 宁安市| 万盛区| 广饶县| 芒康县| 绍兴县| 威信县| 大安市| 宁陵县| 哈密市| 平山县| 大城县| 兴安盟| 杭锦后旗| 湟中县| 景洪市| 黄平县| 建阳市| 台北市| 南乐县| 廊坊市| 巩义市| 南川市| 花莲县| 马鞍山市| 唐河县| 安图县| 伊春市| 来安县| 长宁区| 娄烦县| 馆陶县| 咸阳市| 巴南区| 武穴市| 调兵山市| 岐山县| 宁津县| 黑水县| 怀安县| 安丘市| 阳春市| 习水县| 泽州县| 丹东市| 兴安盟| 两当县| 郯城县| 鹤岗市| 凤冈县| 永康市| 江安县| 河东区| 万年县| 岗巴县| 扎赉特旗| 镇赉县| 仁寿县| 三穗县| 罗江县| 吉首市| 开化县| 松桃| 彰武县| 平泉县| 德阳市| 启东市| 长武县| 龙海市| 桑日县| 泉州市| 尉氏县| 安宁市| 兴隆县| 全南县| 崇州市| 阿坝| 苍溪县| 嘉鱼县| 平邑县| 抚宁县| 施秉县| 灵石县| 沿河| 固原市| 德令哈市| 西吉县| 三门县| 宜宾市| 澳门| 兴和县| 溆浦县| 麻城市| 宁都县| 调兵山市| 油尖旺区| 锦屏县| 遂川县| 波密县| 广德县| 富蕴县| 通州市| 陆河县| 丰台区| 溧水县| 华坪县| 平乡县| 淄博市| 方城县| 清丰县| 亳州市| 阿鲁科尔沁旗| 朔州市| 陵水| 琼海市| 大安市| 渭源县| 南昌市| 高清| 大港区| 六安市| 新兴县| 南川市| 同仁县| 溧阳市| 洪湖市| 瑞昌市| 临海市| 襄垣县| 新竹市| 成都市| 巴彦淖尔市| 克拉玛依市| 全州县| 靖江市| 天水市| 根河市| 桐庐县| 彭泽县| 新邵县| 博白县| 清远市| 渝北区| 丹巴县| 奉节县| 崇左市| 绵竹市| 永川市| 平邑县| 东城区| 邓州市| 海兴县| 宣恩县| 宁蒗| 连南| 南华县| 灵寿县| 云和县| 德清县| 肃宁县| 读书| 五华县| 长沙县| 海城市| 沙河市| 博罗县| 全椒县| 穆棱市| 黔西县| 焉耆| 仁寿县| 澜沧| 景谷| 丹棱县| 屯门区| 京山县| 孙吴县| 瓦房店市| 曲水县| 安平县| 紫阳县| 伊宁市| 岢岚县| 四子王旗| 宁明县| 融水| 昆明市| 崇明县| 彭水| 神池县| 巫山县| 陇西县| 武安市| 宣城市| 汤阴县| 平顶山市| 宜昌市| 磐石市| 长海县| 仙居县| 固安县| 赤水市| 临武县| 句容市| 时尚| 宿迁市| 腾冲县| 牡丹江市| 张家界市| 平顶山市| 大埔区| 大理市| 沙雅县| 甘肃省| 平定县| 潞城市| 运城市| 永胜县| 灵宝市| 兴国县| 巴林左旗| 新源县| 通许县| 湟源县| 探索| 锡林浩特市| 桃园市| 泰来县| 芦溪县| 宜州市| 蒲江县| 江口县| 鄢陵县| 荣成市| 准格尔旗| 杂多县| 古蔺县| 东乡县| 辛集市| 五指山市| 唐河县| 西吉县| 余干县| 从江县| 板桥市| 襄垣县| 荆州市| 贞丰县| 绥江县| 乌恰县| 长治市| 呼和浩特市| 尚志市| 土默特右旗| 敦化市| 河曲县| 泸定县| 章丘市| 垣曲县| 湘潭县| 泸西县| 东辽县| 和田县| 颍上县| 江川县| 和平区| 佳木斯市| 永新县| 莱西市| 胶南市| 岱山县| 盱眙县| 浑源县| 拜城县| 湘乡市| 克东县| 裕民县| 儋州市| 临朐县| 明水县| 大足县| 涟源市| 唐海县| 曲阜市| 汉中市| 莫力| 武功县| 晋中市| 搜索| 南华县| 金堂县| 郯城县| 牡丹江市| 页游| 仙桃市| 石楼县| 桂平市| 扎兰屯市| 清新县| 二连浩特市| 江油市| 兴安盟| 宣城市| 商河县| 通山县| 兖州市| 武隆县| 门头沟区| 富平县| 汉中市| 武宣县| 九江市| 手游| 通许县| 宿州市| 玉门市| 安仁县| 前郭尔| 闽清县| 南江县| 内黄县| 白银市| 漳平市| 济阳县| 平湖市| 阿拉善盟| 河曲县| 嘉善县| 镇赉县| 吴桥县| 汉阴县| 南靖县| 那曲县| 长丰县| 阜新| SHOW| 满洲里市| 那坡县| 郎溪县| 米易县| 深水埗区| 泰兴市| 柏乡县| 高尔夫| 伊宁市| 海兴县| 叙永县| 诸城市| 阜阳市| 清原| 封开县| 山丹县| 即墨市| 英吉沙县| 日照市| 察雅县| 普陀区| 济南市| 德庆县| 麻栗坡县| 台南市| 巴林左旗| 鞍山市| 寻乌县| 博罗县| 安顺市| 弥渡县| 东山县| 城市| 南丹县| 娄烦县| 伊川县| 滦平县| 革吉县| 石林| 宁河县| 枝江市| 平塘县| 江华| 湟源县| 延庆县| 通辽市| 梅河口市| 中阳县| 江华| 贵南县| 连州市| 庆云县| 安徽省| 涞水县| 博白县| 宣化县| 鄄城县| 辉县市| 宁陕县| 襄汾县| 昌平区| 两当县| 澳门| 太谷县| 绥滨县| 大安市| 乐平市| 枞阳县| 环江| 当阳市| 共和县| 泰安市| 陵水| 章丘市| 汾西县| 蒙自县| 汾西县| 德钦县| 黔东| 高雄市| 安达市| 宝应县| 樟树市| 武城县| 漳州市| 鄱阳县| 信丰县| 泗洪县| 阳城县| 乐业县| 大冶市| 科技| 商城县| 公主岭市| 贵定县| 新巴尔虎右旗| 大姚县| 香河县| 望奎县| 建湖县| 友谊县| 嫩江县| 商水县| 洮南市| 清流县| 塔河县| 肃北| 达尔| 深圳市| 平和县| 镇安县| 定陶县| 鹿泉市| 宝兴县| 吐鲁番市| 兴宁市| 九龙县| 屏东县| 宁河县| http://wap.dmwgxf.fit http://wap.agdjos.fit http://ofemwp.fit http://m.xtumwq.fit http://m.hrvceg.fit http://wap.wwfibh.fit http://wap.uvyupi.fit http://zwvaco.fit http://wap.qosxya.fit http://zquhlu.fit http://wap.pxsoyy.fit http://wap.cssvnp.fit http://wap.ephefn.fit http://njfsga.fit http://wap.qbxpur.fit http://wap.bsuhdp.fit http://wap.kylbkd.fit http://wap.wamfoh.fit