考场上打了两个小时树剖,结果还是没搞出来
发现对于两个确定的点,它们一定可以列出一个方程来
其中系数的大小和正负只与这两点间距离的奇偶性有关
所以可以加一堆分情况讨论然后树剖
至于正解:
考虑两点之间的关系很麻烦,可以固定一个基准点,把它们都用 \(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;
}