QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723962#7608. CliquesinksamuraiWA 0ms3552kbC++2315.7kb2024-11-08 05:01:012024-11-08 05:01:01

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 05:01:01]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3552kb
查看
  • [2024-11-08 05:01:01]
  • 提交

answer

#include <bits/stdc++.h>

// cut here
namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder
// cut here

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

// yosupo Vertex Add Path Sum parentheses
//   <https://judge.yosupo.jp/submission/72507>
// References:
//   <https://cp-algorithms.com/graph/hld.html>
//   <https://codeforces.com/blog/entry/53170>
//   <https://ei1333.github.io/luzhiled/snippets/tree/heavy-light-decomposition.html>
//   <https://atcoder.jp/contests/past202010-open/submissions/21473312>
//   <https://math314.hateblo.jp/entry/2014/06/24/220107>
//   <https://qiita.com/Pro_ktmr/items/4e1e051ea0561772afa3>

// HL 分解 (Heavy Light Decomposition)
//   - 頂点に (単位元ではない) 初期値を与える場合の注意点
//     - hld.build() の実行後に行う
//     - 頂点 u は hld 内部では hld.in[u] となることに注意
//   - 辺に値がある場合は子側の頂点に持たせて edge = true で関数を呼び出す
struct HLD {
    int N, root;
    vector<vector<int>> G;
    vector<int> parent;  // 頂点 u の親
    vector<int> depth;  // 頂点 u の深さ
    vector<int> sz;  // 頂点 u を根とする部分木のサイズ (heavy)
    vector<int> in;  // HL 分解時の探索順序 (Euler Tour)
    vector<int> out;  // 後述
    vector<int> head;  // 頂点 u が属する HL 分解後の連結成分の根
    vector<int> rev;  // 探索順序番号から元の頂点番号への逆引き
    int t = 0;  // 探索順序の計算用

    // [ in[u], out[u] )      := 頂点 u を根とする部分木に対応
    // [ in[head[u]], in[u] ] := HL 分解後の連結成分における頂点 u からその head までのパスに対応

    HLD() {}
    HLD(int n, int r = 0) : N(n), root(r) {
        G.resize(N); parent.resize(N); depth.resize(N); sz.resize(N);
        in.resize(N); out.resize(N); head.resize(N); rev.resize(N);
    }

    // 双方向に辺を張る
    void add_edge(int u, int v) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // 各部分木のサイズを求める
    void dfs_sz(int u, int p, int d) {
        parent[u] = p;
        depth[u] = d;
        sz[u] = 1;
        // heavy edge が先頭に来るように維持しながら探索する
        if (G[u].size() && G[u][0] == p) swap(G[u][0], G[u].back());
        for (int& v : G[u]) if (v != p) {  // NOTE: swap のために int& が必要
            dfs_sz(v, u, d + 1);
            sz[u] += sz[v];
            if (sz[G[u][0]] < sz[v]) swap(G[u][0], v);
        }
    }

    // HL 分解 (Heavy Light Decomposition)
    void dfs_hld(int u, int p) {
        in[u] = t++;
        rev[in[u]] = u;
        for (const int& v : G[u]) if (v != p) {
            head[v] = (v == G[u][0] ? head[u] : v);  // heavy or light
            dfs_hld(v, u);
        }
        out[u] = t;
    }

    void build() {
        dfs_sz(root, -1, 0);
        dfs_hld(root, -1);
    }

    // 頂点 u から深さ d だけ親を辿る (level-ancestor) : O(log N)
    // 辿った先が木上にあることを想定している
    //   - d <= depth[u]
    int la(int u, int d) const {
        assert(0 <= u && u < N);
        while (true) {
            int v = head[u];
            if (in[u] - d >= in[v]) return rev[in[u] - d];
            d -= in[u] - in[v] + 1;
            u = parent[v];
        }
    }

    // 頂点 u, v の LCA : O(log N)
    int lca(int u, int v) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        while (true) {
            if (in[u] > in[v]) swap(u, v);  // in[u] <= in[v]  (u が根側)
            if (head[u] == head[v]) return u;
            v = parent[head[v]];
        }
    }

    // (u, v) パス間の辺数 : O(log N)
    int distance(int u, int v) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        return depth[u] + depth[v] - 2*depth[lca(u, v)];
    }

    // 頂点 w が (u, v) パス上に存在するか : O(log N)
    bool on_path(int u, int v, int w) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        assert(0 <= w && w < N);
        return distance(u, w) + distance(w, v) == distance(u, v);
    }

    // パス [u,v] に対する更新クエリ : O((log N)^2)
    template<class F>
    void apply_path(int u, int v, bool edge, const F& func) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        while (true) {
            if (in[u] > in[v]) swap(u, v);  // in[u] <= in[v]  (u が根側)
            if (head[u] == head[v]) break;
            func(in[head[v]], in[v]);
            v = parent[head[v]];
        }
        func(in[u] + edge, in[v]);
    }

    // パス [u,v] に対する取得クエリ : O((log N)^2)
    template <class S, S (*op)(S, S), S (*e)(), class F>
    S prod_path(int u, int v, bool edge, const F& func) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        S Su = e(), Sv = e();
        while (true) {
            if (in[u] > in[v]) { swap(u, v); swap(Su, Sv); }  // in[u] <= in[v]  (u が根側)
            if (head[u] == head[v]) break;
            Sv = op(Sv, func(in[head[v]], in[v]));
            v = parent[head[v]];
        }
        return op(Su, op(Sv, func(in[u] + edge, in[v])));
    }

    // 頂点 u を根とする部分木に対する更新クエリ : O(log N)
    void apply_subtree(int u, bool edge, function<void(int, int)> func) {
        assert(0 <= u && u < N);
        func(in[u] + edge, out[u] - 1);
    }

    // 頂点 u を根とする部分木に対する取得クエリ : O(log N)
    template <class S>
    S prod_subtree(int u, bool edge, function<S(int, int)> func) const {
        assert(0 <= u && u < N);
        return func(in[u] + edge, out[u] - 1);
    }
};

// snuke's mod int
template <ll mod>
struct modint{
	ll x;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

using mint=modint<1000000007>;

typedef vec(mint) vm;

mint op(mint l,mint r){
	return l+r;
}

mint e(){
	return 0;
}

mint mapping(mint l,mint r){
	return l*r;
}

mint composition(mint l,mint r){
	return l*r;
}

mint id(){
	return 1;
}

void slv(){
	int n;
	cin>>n;

	vec(vi) adj(n);
	HLD hld(n,0);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		hld.add_edge(u,v);
		adj[u].pb(v),adj[v].pb(u);
	}
	hld.build();
	bool edge=0;

	vi par(n),dep(n),tin(n),tout(n);
	int _tm=0;
	auto dfs=[&](auto self,int v)->void{
		tin[v]=_tm++;
		for(auto u:adj[v]){
			if(u==par[v]) continue;
			par[u]=v;
			dep[u]=dep[v]+1;
			self(self,u);
		}
		tout[v]=_tm;
	};
	dfs(dfs,0);

	vec(vi) spr(20,vi(n));
	{
		rep(v,n){
			spr[0][v]=par[v];
		}	
		rng(j,1,20){
			rep(v,n){
				spr[j][v]=spr[j-1][spr[j-1][v]];
			}
		}
	}

	auto is_ancestor=[&](int u,int v){
		return tin[u]<=tin[v] and tin[v]<tout[u];
	};

	auto lca=[&](int u,int v)->int{
		if(is_ancestor(u,v)) return u;
		if(is_ancestor(v,u)) return v;
		per(j,20){
			if(!is_ancestor(spr[j][u],v)){
				u=spr[j][v];
			}
		}
		return par[u];
	};

	auto shift=[&](int u,int d)->int{
		per(j,20){
			if(d>>j&1){
				u=spr[j][u];
			}
		}
		return u;
	};

	vec(mint) x(n);
	rep(v,n){
		x[hld.in[v]]=1;
	}
	atcoder::lazy_segtree<mint,op,e,mint,mapping,composition,id> a(x),b(x);

	auto get=[&](int u,int up)->mint{
		mint res=0;
		// while(x!=up){
		// 	res+=a[x];
		// 	res-=b[x];
		// 	x=par[x];
		// }
		if(u==up) return res;
		int d=hld.distance(u,up);
		d-=1;
		int dup=shift(u,d);
		res+=hld.prod_path<mint,op,e>(u, dup, edge, [&](int l, int r) {
			return a.prod(l, r+1);
		});
		res-=hld.prod_path<mint,op,e>(u, dup, edge, [&](int l, int r) {
			return b.prod(l, r+1);
		});
		return res;
	};

	mint inv2=mint(2).inv();
	auto update=[&](int u,int up,int ad){
		if(u==up) return;
		int d=hld.distance(u,up);
		d-=1;
		int dup=shift(u,d);
		hld.apply_path(u, dup, edge, [&](int l, [[maybe_unused]] int r) {
			// seg.set(l, seg.get(l) + x);
			a.apply(l,r+1,ad==1?2:inv2);
		});
		hld.apply_path(u, dup, edge, [&](int l, [[maybe_unused]] int r) {
			// seg.set(l, seg.get(l) + x);
			b.apply(l,r+1,ad==1?2:inv2);
		});
		// while(x!=up){
		// 	if(ad==1){
		// 		a[x]*=2;
		// 		b[x]*=2;
		// 	}else{
		// 		a[x]*=inv2;
		// 		b[x]*=inv2;
		// 	}
		// 	x=par[x];
		// }
	};

	int q;
	cin>>q;
	mint now=0;
	rep(i,q){
		char ch;
		cin>>ch;
		int x,y;
		cin>>x>>y;
		x-=1,y-=1;
		int up=lca(x,y);
		if(ch=='+'){
			mint val=get(x,up)+get(y,up);
			{
				val+=hld.prod_path<mint,op,e>(up, up, edge, [&](int l, int r) {
					return a.prod(l, r+1);
				});
			}
			now+=val;
			update(x,up,1);
			update(y,up,1);
			{
				hld.apply_path(up, up, edge, [&](int l, [[maybe_unused]] int r) {
					// seg.set(l, seg.get(l) + x);
					a.apply(l,r+1,2);
				});
			}
		}else{
			update(x,up,-1);
			update(y,up,-1);
			{
				hld.apply_path(up, up, edge, [&](int l, [[maybe_unused]] int r) {
					// seg.set(l, seg.get(l) + x);
					a.apply(l,r+1,inv2);
				});
			}
			mint val=get(x,up)+get(y,up);
			{
				val+=hld.prod_path<mint,op,e>(up, up, edge, [&](int l, int r) {
					return a.prod(l, r+1);
				});
			}
			now-=val;
		}
		print(now.x);
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t;
	// cin>>t;
	t=1;
	rep(cs,t){
		slv();
	}
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1 
3 
7 
3 
7 
9

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3552kb

input:

20
8 7
19 10
12 14
3 16
17 13
7 10
5 6
1 9
15 12
5 2
16 13
3 11
20 14
18 6
1 14
16 20
11 10
3 4
20 6
30
+ 10 20
+ 14 20
+ 12 17
- 14 20
- 12 17
+ 4 6
+ 8 20
+ 3 6
- 10 20
+ 2 17
+ 1 16
+ 6 10
+ 9 10
+ 5 15
+ 7 8
- 7 8
+ 2 5
+ 3 18
+ 1 20
+ 8 16
- 3 18
- 5 15
+ 4 20
+ 14 16
- 4 6
+ 8 19
+ 4 7
- 1 16
...

output:

1 
3 
7 
3 
1 
4 
12 
40 
8 
40 
94 
222 
458 
946 
948 
946 
950 
1974 
3974 
4230 
2054 
1076 
2228 
4468 
2236 
2252 
2332 
1708 
2204 
1580

result:

wrong answer 6th lines differ - expected: '3', found: '4 '
English 繁體中文 简体中文

Server Time: 2024-12-03 21:34:04 | OpenSource Project