#245112 (C++11) No.235 めぐるはめぐる (5)

提出ソース

結果

問題	No.235 めぐるはめぐる (5)
ユーザー	noshi91
提出日時	2018-03-17 17:27:09
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	994 ms / 10,000 ms
コード長	7,007 bytes
コンパイル時間	1,121 ms
コンパイル使用メモリ	85,496 KB
実行使用メモリ	20,352 KB
最終ジャッジ日時	2024-06-06 10:00:47
合計ジャッジ時間	4,948 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	994 ms 20,352 KB
testcase_01	AC	461 ms 20,336 KB
testcase_02	AC	890 ms 20,316 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <climits>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <type_traits>
#include <utility>
#include <vector>

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;

#include <cassert>
#include <cstdint>
#include <vector>

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;
#include <cassert>
#include <cstdint>
#include <vector>

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;
template <typename Mo, typename Op> class LC {
  struct node {
    node *left, *right, *per;
    Mo data, sum;
    Op lazy;
    bool isroot, rev;
    static node *const nil;
    void push() {
      if (rev) {
        left->rev ^= 1;
        right->rev ^= 1;
        std::swap(left, right);
        data = ~data;
        rev = 0;
      }
      data = data * lazy;
      left->lazy = left->lazy * lazy;
      right->lazy = right->lazy * lazy;
      lazy = Op();
    }
    Mo reflect() const { return rev ? ~sum * lazy : sum * lazy; }
    void fix() {
      if (rev)
        sum = ~sum;
      sum = sum * lazy;
      push();
    }
    void propagate() {
      if (per)
        per->propagate();
      push();
    }
    void haulL(node *const l) {
      left = l;
      l->per = this;
    }
    void haulR(node *const r) {
      right = r;
      r->per = this;
    }
    void splay() {
      node *x = this, *pp = per;
      left->fix();
      right->fix();
      nil->sum = Mo();
      nil->lazy = Op();
      nil->rev = 0;
      while (!x->isroot) {
        if (pp) {
          if (pp->left == x)
            pp->left = this;
          else
            pp->right = this;
        }
        if (per->isroot) {
          if (per->left == this) {
            per->haulL(right);
            per->sum = right->sum + per->data + per->right->reflect();
            right = per;
            x = per;
            per = per->per;
            right->per = this;
          } else {
            per->haulR(left);
            per->sum = per->left->reflect() + per->data + left->sum;
            left = per;
            x = per;
            per = per->per;
            left->per = this;
          }
          break;
        }
        x = per->per;
        pp = x->per;
        if (per->left == this) {
          if (x->left == per) {
            x->haulL(per->right);
            x->sum = x->left->reflect() + x->data + x->right->reflect();
            per->haulR(x);
            per->haulL(right);
            per->sum = right->sum + per->data + x->sum;
            haulR(per);
          } else {
            x->haulR(left);
            x->sum = x->left->reflect() + x->data + left->sum;
            per->haulL(right);
            per->sum = right->sum + per->data + per->right->reflect();
            haulL(x);
            haulR(per);
          }
        } else {
          if (x->right == per) {
            x->haulR(per->left);
            x->sum = x->left->reflect() + x->data + x->right->reflect();
            per->haulL(x);
            per->haulR(left);
            per->sum = x->sum + per->data + left->sum;
            haulL(per);
          } else {
            x->haulL(right);
            x->sum = right->sum + x->data + x->right->reflect();
            per->haulR(left);
            per->sum = per->left->reflect() + per->data + left->sum;
            haulR(x);
            haulL(per);
          }
        }
        per = pp;
      }
      sum = left->sum + data + right->sum;
      x->isroot = 0;
    }
    void expose(node *const prev) {
      splay();
      if (right != nil)
        right->isroot = 1;
      right = prev;
      sum = left->sum + data + right->sum;
      if (per)
        per->expose(this);
      else
        isroot = 1;
    }
  };
  std::vector<node> tree;
  void expose(node *const n) {
    n->propagate();
    n->expose(node::nil);
    n->splay();
    n->isroot = 1;
    n->sum = n->left->sum + n->data + n->right->sum;
  }

public:
  LC(const uint32 size)
      : tree(size, {node::nil, node::nil, nullptr, Mo(), Mo(), Op(), 1, 0}) {}
  LC(const std::vector<Mo> &a)
      : tree(a.size(),
             {node::nil, node::nil, nullptr, Mo(), Mo(), Op(), 1, 0}) {
    for (uint32 i = 0; i < a.size(); ++i)
      tree[i].data = tree[i].sum = a[i];
  }
  void link(uint32 child, uint32 per) {
    evert(child);
    tree[child].per = &tree[per];
  }
  void cut(uint32 child) {
    node *n = &tree[child];
    expose(n);
    n->left->per = nullptr;
    n->left->isroot = 1;
    n->left = node::nil;
    n->sum = n->data;
  }
  void update(uint32 u, uint32 v, const Op &data) {
    evert(u);
    expose(&tree[v]);
    tree[v].lazy = data;
  }
  Mo path(uint32 u, uint32 v) {
    evert(u);
    expose(&tree[v]);
    return tree[v].sum;
  }
  void evert(uint32 v) {
    expose(&tree[v]);
    tree[v].rev ^= 1;
  }
};
template <typename Mo, typename Op>
typename LC<Mo, Op>::node *const LC<Mo, Op>::node::nil = []() {
  LC<Mo, Op>::node *const ret = new LC<Mo, Op>::node;
  ret->left = ret->right = ret;
  ret->data = ret->sum = Mo();
  return ret;
}();
static constexpr uint64 MOD = 1000000007;
struct p {
	uint64 data;
	p(uint64 x=0) :data(x) {}
	p operator*(const p &other)const {
		return p((data + other.data) % MOD);
	}
};
struct meguru {
	uint64 s, c;
	meguru() :s(0), c(0) {}
	meguru(uint64 x, uint64 y) :s(x), c(y) {}
	meguru operator~()const {
		return *this;
	}
	meguru operator+(const meguru &other)const {
		return meguru((s + other.s) % MOD, (c + other.c) % MOD);
	}
	meguru operator*(const p &other)const {
		return meguru((s + c*other.data) % MOD, c);
	}
};

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 n;
	std::cin >> n;
	std::vector<meguru> D(n);
	uint64 s, c;
	for (uint32 i = 0;i < n;++i) {
		std::cin >> s;
		D[i].s = s;
	}
	for (uint32 i = 0;i < n;++i) {
		std::cin >> c;
		D[i].c = c;
	}
	LC<meguru, p> L(D);
	uint32 a, b;
	for (uint32 i = 1;i < n;++i) {
		std::cin >> a >> b;
		L.link(a - 1, b - 1);
		//L.scan();
	}
	uint32 q;
	std::cin >> q;
	uint64 que, x, y, z;
	while (q--) {
		std::cin >> que >> x >> y;
		if (que) {
			std::cout << L.path(x - 1, y - 1).s << "\n";
		}
		else {
			std::cin >> z;
			L.update(x - 1, y - 1, p(z));
		}
		//L.scan();
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード