求助哪里没开 long long
  • 板块灌水区
  • 楼主haochengw920
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/2 10:13
  • 上次更新2024/8/2 11:23:13
查看原帖
求助哪里没开 long long
563650
haochengw920楼主2024/8/2 10:13

rt , #define int long long 就过了, 删了就 Wa 了

另:有什么类似 cf 的方法可以快速找到越界吗?

#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define int long long
#define Mod (998244353)
using namespace std;

namespace Fast_OI {
	char buf[1000000], *p1 = buf, *p2 = buf, obuf[1000000], *p3 = obuf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
	#define putchar(x) (p3-obuf<1000000?*p3++=x:(fwrite(obuf,1,p3-obuf,stdout),p3=obuf,*p3++=x))
	inline int read() {
		int x = 0; bool f = 1; char c = getchar();
		while (!isdigit(c)) { if (c == '-') f = 0; c = getchar(); }
		while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
		return f ? x : -x;
	}
	inline void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + 48);
	}
} using namespace Fast_OI;

const int MAXN = 500005;

int n, m;
int dep[MAXN];
vector<int>link[MAXN];
struct edge {
	int to, nex;
}e[MAXN << 1]; int idx, head[MAXN];
inline void add(int u, int v) {
	e[++ idx].to = v;
	e[idx].nex = head[u];
	head[u] = idx; 
}

namespace President_tree {
	#define lc sons[u][0]
	#define rc sons[u][1]
	struct Node {
		int sum, tlz;
	}tr[MAXN * 20]; int idx;
	int rt[MAXN], sons[MAXN * 20][2];
	inline void push_up(int u) {
		tr[u].sum = (tr[lc].sum + tr[rc].sum) % Mod;
	}
	inline void push_down(int u) {
		int tg = tr[u].tlz; tr[u].tlz = 1;
		(tr[lc].sum *= (ll)tg) %= Mod, (tr[lc].tlz *= (ll)tg) %= Mod;
		(tr[rc].sum *= (ll)tg) %= Mod, (tr[rc].tlz *= (ll)tg) %= Mod;
	}
	inline void Modify(int &u, int p, int x, int l = 0, int r = n) {
		if (!u) u = ++ idx; tr[u].tlz = 1;
		if (l == r) {
			tr[u].sum = x;
			return;
		} push_down(u); int mid = (l + r) >> 1;
		if (p <= mid) Modify(lc, p, x, l, mid);
		else Modify(rc, p, x, mid + 1, r);
		push_up(u);
	}
	inline int Query(int u, int bg, int nd, int l = 0, int r = n) {
		if (!u) return 0;
		if (bg <= l && r <= nd) return tr[u].sum;
		push_down(u); int mid = (l + r) >> 1, res = 0;
		if (bg <= mid) (res += Query(lc, bg, nd, l, mid)) %= Mod;
		if (nd > mid) (res += Query(rc, bg, nd, mid + 1, r)) %= Mod;
		return res;
	}
	inline int Merge(int u, int v, int &su, int &sv, int l = 0, int r = n) {
		if (!u || !v) {
			(su += tr[u].sum) %= Mod, (sv += tr[v].sum) %= Mod; 
			(tr[u].sum *= (ll)sv) %= Mod, (tr[v].sum *= (ll)su) %= Mod;
			(tr[u].tlz *= (ll)sv) %= Mod, (tr[v].tlz *= (ll)su) %= Mod;
			return u + v; 
		} if (l == r) {
			(sv += tr[v].sum) %= Mod; 
			tr[v].sum = ((ll)tr[u].sum * sv + (ll)tr[v].sum * su) % Mod;
			return (su += tr[u].sum) %= Mod, v;
		} push_down(u); push_down(v); int mid = (l + r) >> 1;
		lc = Merge(lc, sons[v][0], su, sv, l, mid);
		rc = Merge(rc, sons[v][1], su, sv, mid + 1, r);
		return push_up(u), u;
	}
	#undef lc
	#undef rc
} using namespace President_tree; 

inline void dfs(int u, int fath) {
	dep[u] = dep[fath] + 1; int mx = 0; 
	for (int v : link[u]) mx = max(mx, dep[v]); 
	Modify(rt[u], mx, 1); 
	for (int i = head[u]; i; i = e[i].nex) {
		int v = e[i].to; 
		if (v == fath) continue; 
		dfs(v, u); 
		int su = 0, sv = Query(rt[v], 0, dep[u]); 
		rt[u] = Merge(rt[u], rt[v], su, sv); 
	}
}

signed main()
{
	n = read(); 
	for (int i = 1; i < n; ++ i) {
		int u = read(), v = read(); 
		add(u, v); add(v, u); 
	} m = read(); 
	for (int i = 1; i <= m; ++ i) {
		int u = read(), v = read(); 
		link[v].emplace_back(u); 
	} dfs(1, 0); 
	write(Query(rt[1], 0, 0)), putchar('\n'); 
	return fwrite(obuf,1,p3-obuf,stdout), 0;
}
2024/8/2 10:13
加载中...