题解 Equation

考场上打了两个小时树剖，结果还是没搞出来

发现对于两个确定的点，它们一定可以列出一个方程来

其中系数的大小和正负只与这两点间距离的奇偶性有关

所以可以加一堆分情况讨论然后树剖

至于正解：

考虑两点之间的关系很麻烦，可以固定一个基准点，把它们都用 \(x_1\) 表示出来

当需要极其麻烦地考虑两点之间的关系时，考虑固定一个基准点分别表示它们

发现这样的话对一个点的修改等价于把它的子树整体加上一个数

所以可以建立dfs序，直接树状数组维护，同样根据奇偶性判无解

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 1000010

#define ll long long

//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, q;

int head[N], size, in[N], out[N], tot, val[N], dep[N], lim;

ll a[N<<1], b[N<<1];

struct edge{int to, next;}e[N];

inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;}

inline void upd(ll* a, int i, ll dat) {for (; i<=lim; i+=i&-i) a[i]+=dat;}

inline ll query(ll* a, int i) {ll ans=0; for (; i; i-=i&-i) ans+=a[i]; return ans;}

void dfs(int u) {

	in[u]=++tot;

	upd(a, in[u], (dep[u]&1?-1:1)*val[u]);

	upd(b, in[u], (dep[u]&1?1:-1)*val[u]);

	for (int i=head[u]; ~i; i=e[i].next) dep[e[i].to]=dep[u]+1, dfs(e[i].to);

	out[u]=++tot;

	upd(a, out[u], (dep[u]&1?1:-1)*val[u]);

	upd(b, out[u], (dep[u]&1?-1:1)*val[u]);

}

signed main()

{

	memset(head, -1, sizeof(head));

	ll w;

	n=read(); q=read(); lim=n*2;

	for (int i=2,u,w; i<=n; ++i) {

		u=read(); w=read();

		add(u, i); val[i]=w;

	}

	dep[1]=1; dfs(1);

	for (int i=1,u,v,s,dlt; i<=q; ++i) {

		if (read()&1) {

			u=read(); v=read(); s=read();

			//cout<<"uv: "<<u<<' '<<v<<endl;

			w=query(dep[u]&1?b:a, in[u])+query(dep[v]&1?b:a, in[v])-s;

			//cout<<"w: "<<w<<' '<<query(dep[u]&1?b:a, in[u])<<' '<<query(dep[v]&1?b:a, in[v])<<endl;

			if (w&1) puts("none");

			else if ((dep[u]&1?1:0)^(dep[v]&1?1:0)) puts(!w?"inf":"none");

			else printf("%lld\n", (((dep[u]&1)&&(dep[v]&1))?-1:1)*(w>>1));

		}

		else {

			u=read(); w=read();

			dlt=w-val[u];

			upd(a, in[u], (dep[u]&1?-1:1)*dlt);

			upd(b, in[u], (dep[u]&1?1:-1)*dlt);

			upd(a, out[u], (dep[u]&1?1:-1)*dlt);

			upd(b, out[u], (dep[u]&1?-1:1)*dlt);

			val[u]=w;

		}

	}

	return 0;

}

巴特西

题解 Equation

最新文章

热门文章