【BZOJ 3672】[NOI2014] 购票

解题报告

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809

解题报告

一句话题解:树上CDQ分治

先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$

我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;
const LL INF = 6e18;

int n, head[N], nxt[M], to[M], fa[N];
LL q[N], p[N], len[N], dep[N], f[N];

struct Point{
	LL x, y, id, range;
	inline Point() {
	}
	inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) {
	}
	inline bool operator < (const Point &P) const {
		return x > P.x || (x == P.x && y > P.y);
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y, 0, 0);
	}
	inline double operator * (const Point &P) {
		return (double)x * P.y - (double)y * P.x;
	}
	inline double slope(const Point &P) {
		return (double)(y - P.y) / (x - P.x);
	}
	static bool update(const Point &P1, const Point &P2) {
		return P1.range > P2.range;
	}
};

inline LL read() {
	char c = getchar(); LL ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

class DivideAndConquer{
int sz[N], vis[N];
public:	
	inline void solve(int w, int universe) {
		int top = w;
		vis[w = FindRoot(w, universe)] = 1;
		if (fa[w] && !vis[fa[w]]) {
			solve(top, universe - sz[w]);
		}
		vector<Point> cvx;
		for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) {
			cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw]));
		}
		vector<Point> que;
		que.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				DFS(to[i], w, que);
			}	
		}	
		
		sort(que.begin(), que.end(), Point::update);
		sort(cvx.begin(), cvx.end());
		for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) {
			for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) {
				for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot);
				cvx[tot++] = cvx[j];
			}
			int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id;
			while (l <= r) {
				mid = l + r >> 1;
				if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) {
					ret = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			if (ret >= 0) {
				f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]);
			}
		}
		for (int i = 0, j; i < (int)que.size(); i++) {
			if (j = que[i].id, que[i].range <= dep[w]) {
				f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]);
			}
		}
		que.clear();
		cvx.clear();
	
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				solve(to[i], sz[to[i]]);
			}
		}	
	}	
private:
	inline int FindRoot(int w, int universe) {
		int ret = 0, ans;
		FindRoot(w, w, universe, ret, ans);
		return ret;
	}	
	inline void FindRoot(int w, int f, int universe, int &ret, int &ans) {
		int mx = 1; sz[w] = 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				FindRoot(to[i], w, universe, ret, ans);
				sz[w] += sz[to[i]];
				mx = max(mx, sz[to[i]]);
			}
		}
		mx = max(mx, universe - sz[w]);
		if (!ret || mx < ans) {
			ans = mx;
			ret = w;
		}
	}
	inline void DFS(int w, int f, vector<Point> &ret) {
		ret.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, ret);
			}
		}
	}
}DAC;

int main() {
	n = read(); read();
	for (int i = 2; i <= n; i++) {
		fa[i] = read();
		LL c = read(); AddEdge(fa[i], i);
		p[i] = read(); q[i] = read();
		len[i] = read();
		dep[i] = dep[fa[i]] + c;
	}
	fill(f, f + N, INF);
	f[1] = 0; dep[0] = -1;
	DAC.solve(1, n);
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", f[i]);
	}
	return 0;
}

【BZOJ 3451】Tyvj1953 Normal

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3451
神犇题解:http://wyfcyx.is-programmer.com/posts/74735.html

解题报告

考虑一个点$u$,如果点分到点$v$的时候会产生贡献
那么点分$v$的时候,$v \to u$这个路径上还没有其他点被点分
换一句话来讲,点$v$应该是$v \to u$这条路径上第一个被点分的点
因为每一个点被选的概率一样,所以贡献的概率是$\frac{1}{dis_{u \to v} + 1}$
于是最后答案就是$\sum\limits_{u,v \in [1,n]}{\frac{1}{dis_{u \to v}+1}}$

然后这个东西我们可以使用点分治加上FFT来解决
具体来讲就是在点分的时候统计$dis_{u \to v}=x$的方案数,然后计入答案
时间复杂度:$O(n \log^2 n)$

—————————— UPD 2017.4.11 ————————————
找到这题的序列版了:http://www.lydsy.com/JudgeOnline/problem.php?id=2769
在具体的做法方面,用分个块,然后块内暴力,块间FFT即可

【BZOJ 4182】Shopping

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4182
神犇题解:http://www.cnblogs.com/clrs97/p/4676134.html

解题报告

这个是一个多重背包,于是我们定义$f_{i,j}$为走到第$i$个点,花费$j$元的最大收益
我们先搞出一个DFS序,现在对于点$i$我们可以选或不选
若选,那么我们转移到DFS序的下一个去
若不选,那么我们需要跳过他的整个子树——这在DFS序上是一段连续的区间
于是我们就可以在$O(nm \log d)$的时间复杂度内解决这个问题了

另外Claris的点分的做法也非常好玩啊
通用性还要更强一点,提供了一种新的思路

—————————— UPD 2017.3.19 ——————————
这题今天写了写代码,似乎不能直接DP,会有一系列问题
将上述DP套个点分就没有问题了,不过套点分的话,就直接像Claris那么做就好啦
总之复杂度似乎还是只能做到$O(nm \log n \log m)$

【日常小测】路径规划

题目大意

给定一棵$n(n \le 3 \cdot 10^5)$个点无根带边权的树
要求找出一条路径使得该路径上边权的最小值乘边权和最大

解题报告

这题啊!我们可以无脑点分对不对啊?
时间复杂度$O(n \log ^2 n)$,卡卡常数能过去

但这题更优雅的做法是维护直径
就像51nod上一个题一样,每一块内搞一个直径
合并两个块后生成的大块的直径一定在这四个点之间
于是就一路合并上去就可以辣!
时间复杂度:$O(n \log n)$

Code

点分治版本:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300009;
const int M = N << 1;
const int INF = 1e9;
 
int n,head[N],nxt[M],to[M],cost[M];
LL vout;
 
inline void Add_Edge(int u, int v, int c) {
    static int E = 1; 
    to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
class Divide_and_Conquer{
    int rt,rt_sz,blk_sz,tot,sz[N],vis[N];
    struct Data{
        int mn,id; LL sum;
        inline bool operator < (const Data &B) const {
            return mn < B.mn;
        }
    }sta[N];
    public:
        void solve(int w, int blk) { 
            GetRoot(w, blk); vis[w=rt] = 1; tot = 0;
            for (int i=head[w];i;i=nxt[i]) {
                if (!vis[to[i]]) {
                    DFS(to[i], w, to[i], cost[i], cost[i]);
                }
            } 
            if (tot) update(); 
            for (int i=head[w];i;i=nxt[i]) {
                if (!vis[to[i]]) { 
                    if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w];
                    solve(to[i], sz[to[i]]);
                }
            }
        }
    private:
        inline void update() {
            sort(sta+1, sta+1+tot);
            LL mx1=0,mx2=0; int sur1=0,sur2=0;
            for (int i=tot;i;i--) {
                vout = max(vout, sta[i].mn * sta[i].sum);
                if (sur1 && sur1 != sta[i].id) {
                    vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn);
                } else if (sur2 && sur2 != sta[i].id) {
                    vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn);
                }
                if (sta[i].sum > mx1) {
                    if (sur1 == sta[i].id) {
                        mx1 = sta[i].sum;
                    } else {
                        mx2 = mx1; sur2 = sur1;
                        mx1 = sta[i].sum; sur1 = sta[i].id;
                    }
                } else if (sta[i].sum > mx2) {
                    if (sur1 != sta[i].id) {
                        sur2 = sta[i].id;
                        mx2 = sta[i].sum;
                    }
                }
            }
        }
        inline void GetRoot(int w, int blk) {
            rt_sz = INF; blk_sz = blk;
            GetRoot1(w, w); 
        }
        void GetRoot1(int w, int f) {
            sz[w] = 1; int mx = 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f && !vis[to[i]]) {
                    GetRoot1(to[i], w);
                    sz[w] += sz[to[i]];
                    mx = max(mx, sz[to[i]]);
                }
            }
            mx = max(mx, blk_sz - sz[w]);
            if (mx < rt_sz) rt_sz = mx, rt = w;
        }
        void DFS(int w, int f, int top, int mn, LL sum) {
        	bool tag = 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f && !vis[to[i]]) {
                    DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum);
				}
            }
            if (!tag) return;
            sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum;
        }
}DAC;
 
int main() {
    n = read();
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        Add_Edge(u, v, read());
    }
    DAC.solve(1, n);
    printf("%lld\n",vout);
    return 0;
}

维护直径版本:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009; 
const int M = N << 1;

int n,head[N],nxt[M],to[M],cost[M];
int stp[N],p[N][2],fa[N][20],anc[N];
struct Edge{int u,v,c;}e[N];
LL vout,dep[N],MX[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void DFS(int w, int f) {
	fa[w][0] = f; stp[w] = stp[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dep[to[i]] = dep[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline void AddEdge(int u, int v, int c, int id) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
	e[id] = (Edge){u, v, c};
}

inline LL Dis(int u, int v) {
	if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v;
	for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i];
	if (u == v) return dep[p2] - dep[u];
	for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2];
}

int find(int x) {return anc[x]==x?x:anc[x]=find(anc[x]);}

inline LL Merge(int u, int v) {
	static LL ret, p1, p2; u = find(u); v = find(v);
	if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1];
	else ret = MX[v], p1 = p[v][0], p2 = p[v][1]; 
	for (int i=0;i<=1;i++) {
		for (int j=0;j<=1;j++) {
			LL cur = Dis(p[u][i], p[v][j]);
			if (cur > ret) {
				ret = cur; 
				p1 = p[u][i];
				p2 = p[v][j];
			}
		}
	}
	anc[u] = v; MX[v] = ret;
	p[v][0] = p1; p[v][1] = p2;
	return ret;
}

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read(), i);
	} 
	DFS(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;});
	for (int i=1;i<=n;i++) {
		anc[i] = i;
		p[i][0] = p[i][1] = i;
	}	
	for (int i=1;i<n;i++) {
		LL tmp = Merge(e[i].u, e[i].v);
		vout = max(vout, tmp * e[i].c);
	}
	printf("%lld\n",vout);
	return 0;
}

【HackerRank】Unique Colors

相关链接

题目传送门:https://www.hackerrank.com/challenges/unique-colors
题目大意:http://paste.ubuntu.com/23686184/
官方题解:https://www.hackerrank.com/challenges/unique-colors/editorial

解题报告

Ⅰ.点分治的做法 \(O(n\log (n))\)

先考虑一种较为简单的情况:只有一种颜色
询问有多少对节点间至少存在一个点被染色

直接考虑点分治的做法的话
设当前的分治点为1
定义\({T_i}\)为点i的子树中到1号点的路径上有点被染色的点的数量
定义\({S_i}\)为点i的子树中点的个数

考虑此时对 点3 的贡献:

  1. 点3点1 的简单路径上没有染色点
    那么贡献为\({T_1} – {T_3}\)
  2. 点3点1 的简单路径上有染色点
    那么贡献为\({S_1} – {S_2}\)

这样的话,只有一种颜色的情况就解决了
现在考虑有多种颜色:

不难发现对于一个固定点i,颜色只需要分两类:
1. 到分支点的路径上出现过该颜色
2. 到分治点的路径上没有出现过该颜色

这样的话,我们发现只需要一次DFS就可以解决这个问题
于是就可以使用点分治解决这个问题啦!

Ⅱ. DFS序的做法 \(O(n)\)

先来考虑一个简单一点的版本:假如这货是在序列上
考虑每一种颜色单独处理的话,就是将序列分成几块,每一块的贡献不同
现在重新考虑树上的版本,其实也是把整个树分成好几块
酱紫的话,我们唯一需要解决的就是如何给树上一个连通块统一加上一个数

我们发现我们可以先搞出一个最小的包含“需要更改的连通块”的子树
然后去掉一些子树来删掉多余的部分
子树操作的话,在DFS序上是连续的,于是打差分就好
因为题目的特殊性,不难发现需要删掉的子树总共只会有\(O(n)\)个
于是此题就 \(O(n)\) 辣!

Code

好像两种写法都不是特别好写的样子
于是就不写代码辣!

【CodeChef BTREE】Union on Tree

相关链接

题目传送门:https://www.codechef.com/problems/BTREE
数据生成器:http://paste.ubuntu.com/23671176/
中文题面:http://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf
官方题解:https://discuss.codechef.com/questions/53273/btree-editorial
神犇题解Ⅰ:http://xllend3.is-programmer.com/posts/64760.html
神犇题解Ⅱ:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

WJMZBMR Orz

又是 青年计算机科学家陈立杰 出的神题!
真的是跪烂!_(:з」∠)_

解题报告

看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来,那么剩下的问题就是在利用虚树的边来统计答案了

1)函数式线段树的做法

考虑k=1,这样的话不用处理重复的问题,于是直接点分治就可以做
但现在有很多的点,于是我们可以将树剖成很多块,每块中恰好又一个城市a有卫兵
更进一步,我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话,就可以不用考虑去重的问题了

我们再仔细观察一下建出来的虚树,发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点,统计一下、加到答案里去
对于a所在联通块的其余边缘节点,再统计一下、从答案中减去

于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑:

  1. v不是u在虚树中的祖先,统计v的子树中、到u的距离为d的点的个数
    这个的话,直接用函数式线段树查就好
  2. v是u的父亲,其余条件相同
    这样的话,似乎与v的距离就不固定了(lca在u ~ v中移动)
    于是先用点分治做出所有点到u的距离为d的点的个数n1
    然后需要减掉v子树外的部分,这样的话,发现到v的距离就固定了
    于是减掉所有点到v的距离为d-dis(u,v)的点数n2
    再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣!

2)直接用点分治的做法

先用把点分树搞出来,这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 (不会的同学可以先去做BZOJ_3730

再考虑把虚树建出来,这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集,那么就肯定没有重复
如果有交集,那么设交集的重点为m,交集半径为r'那么直接减掉dis(m,r')就可以辣!

另外还需要预先将完全包含的管辖区间给修改成“相切”的情况,这样才能保证去重完整
还有的话,中点可能落在边上,于是可以在每边的中点加一个点

这样的做法是不是比主席树的做法清真了很多?
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话,这题就很难这样做了

Code

最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}
		
inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f) {
	static int cnt = 0;
	dep[w] = dep[f] + 1;
	anc[w][0] = f; num[w] = ++cnt;
	for (int i=head[w];i;i=nxt[i]) {
		if (!dep[to[i]]) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) 
		if (dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	} 
	return anc[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
	int fa[N][18],tot[N],sum[N];
	int ans_tmp,root,block_size;
	vector<int> q[N],mul[N];
	bool vis[N];
	
	public: 	
		inline void init() {
			block_size = n;
			ans_tmp = INF;
			Get_Root(1, 1);
			tot[root] = 1;
			build(root, n);	
		}
		
		inline int query(int w, int rag) {
			int ret = Query(w, rag, q);
			for (int i=1,t;i<tot[w];i++) {
				t = rag - dis(fa[w][i], w);
				if (t >= 0) {
					ret += Query(fa[w][i], t, q);
					ret -= Query(fa[w][i-1], t, mul);
				}
			}
			return ret;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					mx = max(mx, sum[to[i]]);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(block_size - sum[w], mx);
			if (mx < ans_tmp) {
				ans_tmp = mx;
				root = w;
			}
		}
		
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
					ans_tmp = INF; Get_Root(to[i], w);
					memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
					tot[root] = tot[w] + 1;
					build(root, block_size);
				}
			}
			
			if (val[w]) {
				for (int i=0;i<tot[w];i++) 
					q[fa[w][i]].push_back(dis(w, fa[w][i]));
				for (int i=0;i<tot[w]-1;i++)
					mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));	
			}
			sort(q[w].begin(), q[w].end());
			sort(mul[w].begin(), mul[w].end());
		} 
		
		inline int Query(int w, int r, vector<int> *a) {
			return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
		}
}PDC; 

class Virtual_Tree{
	int stk[N],rag[N],top,lca,cnt,root;
	queue<int> que;
	bool inq[N];
	
	public:	
		inline void build(int &tot) {
			cnt = tot; T = 0;
			root = p[1] = read(); 
			newnode(p[1], read());
			for (int i=2;i<=tot;i++) {
				p[i] = read();
				newnode(p[i], read());
				root = LCA(root, p[i]);
			}
			static auto cmp = [](int a, int b) {return num[a] < num[b];};
			sort(p+1, p+1+tot, cmp);
			if (root != p[1]) p[++tot] = root, newnode(root, -1);
			stk[top=1] = root;
			for (int i=1+(p[1]==root);i<=cnt;i++) {
				lca = LCA(p[i], stk[top]);
				for (;dep[stk[top]] > dep[lca];top--) 
					if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
					else newnode(lca, -1), AddEdge(lca, stk[top]);
				if (lca != stk[top]) 
					stk[++top] = p[++tot] = lca;
				if (p[i] != stk[top])
					stk[++top] = p[i];
			}
			for (int i=1;i<top;i++)
				AddEdge(stk[i], stk[i+1]);
		}
		
		inline int solve(int tot) {
			prework(tot);
			int ret = 0;
			for (int i=1,u,v,r,mid,t;i<T;i+=2) {
				u = to[i]; v = to[i+1];
				r = rag[u] + rag[v] - cost[i] >> 1;
				if (r >= 0) {
					mid = move(u, v, r);
					ret -= PDC.query(mid, r);
				}
			} 
			for (int i=1;i<=tot;i++) 
				ret += PDC.query(p[i], rag[p[i]]);
			return ret;
		}
	private:
		inline void newnode(int w, int v) {
			rag[w] = v << 1;
			head[w] = 0;
		}
		
		inline int move(int x, int y, int r) {
			if (dep[x] < dep[y]) swap(x, y);
			r = rag[x] - r;
			for (int i=0;r;i++,r>>=1)
				if (r & 1) x = anc[x][i];
			return x;	 
		}
		
		inline void prework(int tot) {
			for (int i=1;i<=tot;i++) {
				que.push(p[i]);
				inq[p[i]] = 1;
			}
			
			while (!que.empty()) {
				int w = que.front(); 
				que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (rag[w] > rag[to[i]] + cost[i]) {
						rag[to[i]] = rag[w] - cost[i];
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
		}
		
		inline void AddEdge(int u, int v) {
			int w = dis(u, v);
			to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
			to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
		}
}VT; 

int main() {
	n = read();
	fill(val+1, val+1+n, 1);
	for (int i=1,lim=n,u,v;i<lim;i++) {
		u = read(); v = read();
		Add_Edge(u, ++n);
		Add_Edge(n, v);
	}
	
	DFS(1, 1);
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			anc[i][j] = anc[anc[i][j-1]][j-1];
		}
	}
	PDC.init();
	
	m = read();
	for (int y=1,k;y<=m;y++) {
		VT.build(k = read());
		printf("%d\n",VT.solve(k)); 
	}
	return 0;
}

【BZOJ 3924】[ZJOI2015] 幻想乡战略游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3924
神犇题解:http://www.cnblogs.com/clrs97/p/4779754.html
官方题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

考虑从根开始向下走
如果一个儿子的子树的权值和大于总和的一半
那么所求的点一定在这个儿子的子树中
由此可见,实际上我们所求的是这样的点:

深度最大的,子树权值和大于总权值和一半的点

这样的话,暴力找复杂度不稳定
考虑树链剖分的话,可以在\({\log ^2}(n)\)的时间复杂度内找到答案
最后考虑输出解的话,似乎直接用树链剖分不行的样子
于是似乎还得用一个点分治? (・∀・(・∀・(・∀・*)

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int L = 18;
const int INF = 1e9;

int n,m,head[N],nxt[M],to[M],cost[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}

class Heavy_Light_Decomposition{
	int dep[N],dis[N],fa[N],top[N],sz[N];
	int go[N],pos[N],len[N],sum,cnt;
	vector<int> que[N];
	class Fenwick_Tree{
		#define lowbit(x) ((x)&-(x))
		int arr[N];
		public:
			inline void modify(int l, int r, int delta) {
				modify(l-1, -delta);
				modify(r, delta);
			}
			inline int query(int p) {
				LL ret = 0;
				for (int i=p;i<=n;i+=lowbit(i))
					ret += arr[i];
				return ret;
			}
		private:
			inline void modify(int p, int delta) {
				for (int i=p;i;i-=lowbit(i))
					arr[i] += delta;
			}
	}BIT;
	public:
		inline void init() {
			DFS1(1, 1);
			DFS2(1, 1, 1);
		}
		inline int DIS(int u, int v) {
			int lca = LCA(u, v);
			return dis[u] + dis[v] - (dis[lca] << 1);	
		}
		inline void modify(int w, int v) {
			sum += v;
			for (;w;w=fa[top[w]]) 
				BIT.modify(pos[top[w]], pos[w], v);
		}
		inline int query() {
			int w = 1, tag = 1;
			while (tag) {
				int l = 1, r = len[w]-1, mid, ret = 0;
				while (l <= r) {
					mid = l + r >> 1;
					if (BIT.query(pos[que[w][mid]])*2 <= sum) r = mid - 1;
					else l = mid + 1, ret = mid;
				} 
				w = que[w][ret]; tag = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (dep[to[i]] > dep[w] && BIT.query(pos[to[i]])*2 > sum) {
						tag = 1; w = to[i]; break;
					}
				}
			}
 			return w;
		}
	private:
		void DFS1(int w, int f) {
			sz[w] = 1; dep[w] = dep[f] + 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f) {
					dis[to[i]] = dis[w] + cost[i];
					fa[to[i]] = w;
					DFS1(to[i], w);
					sz[w] += sz[to[i]];
					if (sz[to[i]] > sz[go[w]])
						go[w] = to[i];
				}
			}
		}
		void DFS2(int w, int f, int t) {
			que[t].push_back(w);
			top[w] = t;	pos[w] = ++cnt;
			if (go[w]) DFS2(go[w], w, t);
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && to[i] != go[w]) {
					DFS2(to[i], w, to[i]);
				}
			}
			len[w] = que[w].size();
			que[w].push_back(w);
		}
		inline int LCA(int u, int v) {
			while (top[u] != top[v]) 
				if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
				else v = fa[top[v]];
			return dep[u] > dep[v]? v: u;
		}
}HLD;

class Vertex_Based_Divide_and_Conquer{
	int sum[N],vis[N],len[N],fa[N][L],rod[N][L];
	int root,size,cur,val_sum[N],val_sum_del[N];
	LL part_ans[N],part_ans_del[N];
	public:
		inline void init() {
			int rt = Get_Root(1, n);
			len[rt] = 1;
			build(rt, n);
		}
		inline void modify(int w, int v) {
			val_sum[w] += v;
			for (int i=1,p=w,d,u;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				val_sum[p] += v;
				val_sum_del[u] += v;
				part_ans[p] += (LL)v * d;
				part_ans_del[u] += (LL)v * d;
			}
		}
		inline LL query(int w) {
			LL ret = part_ans[w];
			for (int i=1,p=w,u,d;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				ret += part_ans[p] + (LL)val_sum[p] * d;
				ret -= part_ans_del[u] + (LL)val_sum_del[u] * d;
			}
			return ret;
		} 
	private:
		inline int Get_Root(int w, int sz) {
			size = sz; cur = INF;
			Get_root(w, w);
			return root;
		}
		void Get_root(int w, int f) {
			int mx = 1; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				}
			}
			mx = max(mx, size - sum[w]);
			if (mx < cur) cur = mx, root = w;
		}
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=1;i<len[w];i++) 
				rod[w][i] = HLD.DIS(w, fa[w][i]);
			for (int i=head[w],tmp,rt;i;i=nxt[i]) {
				if (!vis[to[i]]) {
					tmp = sum[to[i]]<sum[w]? sum[to[i]]: sz-sum[w];
					rt = Get_Root(to[i], tmp);
					len[rt] = len[w] + 1;
					memcpy(fa[rt]+1, fa[w], sizeof(int)*len[w]);
					build(rt, tmp);
				}
			}
		}
		
}VDC;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	HLD.init();
	VDC.init();
	for (int i=1,p,v;i<=m;i++) {
		p = read(); v = read();
		HLD.modify(p, v);
		VDC.modify(p, v);
		p = HLD.query();
		printf("%lld\n",VDC.query(p));
	}
	return 0;
}

【HDU 5571】tree

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5571
数据生成器:http://paste.ubuntu.com/23672970/
中文题面:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=651&pid=1004
官方题解:https://oi.qizy.tech/?attachment_id=2084

解题报告

看到位运算,首先想到的就是一位一位独立来搞
酱紫的话,这题就非常简单了
直接上点分树,什么数据结构都不用套,记录零一就可以了

值得注意的是,拆二进制最好拆在最外层
因为拆在里面的话,数组会多一维,寻址的时间消耗大大增加
否则会T到死,不要问我是怎么知道的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 30000+9;
const int M = N << 1;
const int L = 16;
const int INF = 1e9;

int n,m,T,head[N],to[M],nxt[M],cost[M],ori[N];
int val[N],dep[N],dis[N],fa[N][L],P[N],V[N];
LL ans[N];

inline void Add_Edge(int u, int v, int w) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int w, int f) {
	dep[w] = dep[f] + 1;
	fa[w][0] = f;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f)  {
			dis[to[i]] = dis[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i=L-1;~i;i--) {
		if (dep[fa[u][i]] >= dep[v]) {
			u = fa[u][i];
		}
	}
	if (u == v) return u;
	for (int i=L-1;~i;i--) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}

inline int DIS(int u, int v) {
	int lca = LCA(u, v);
	return dis[u] + dis[v] - dis[lca] * 2;
}

class Node_Based_Divide_and_Conquer{
	int area_sz,cur_ans,root,rod[N][L],sum[N];
	int anc[N][L],len[N],tos[2][N],tot[2][N];
	bool vis[N]; LL f[2][N],sub[2][N];
	
	public:
		inline void init() {
			memset(vis,0,sizeof(vis));
			cur_ans = INF; area_sz = n;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		
		inline void prework() {
			memset(f, 0 ,sizeof(f));
			memset(sub, 0, sizeof(sub));
			memset(tot, 0, sizeof(tot));
			memset(tos, 0, sizeof(tos));
		}
		
		inline void modify(int w, int t, int p) {
			for (int i=0,pre,cur;i<len[w];i++) {
				cur = anc[w][i];
				f[t][cur] += rod[w][i] * p;
				tot[t][cur] += p;
				if (i) {
					pre = anc[w][i-1];
					sub[t][pre] += rod[w][i] * p;
					tos[t][pre] += p;
				}
			}
		}
		
		inline LL query(int w, int t, int k) {
			LL ret = 0,s,d; t ^= 1;
			ret += f[t][w] << k;
			for (int i=1,cur,pre;i<len[w];i++) {
				cur = anc[w][i]; pre = anc[w][i-1];
				d = f[t][cur] - sub[t][pre];
				s = tot[t][cur] - tos[t][pre];
				ret += d + s * rod[w][i] << k;
			}
			return ret;
		} 
	private:
		void Get_Root(int w, int F) {
			sum[w] = 1; int mx = 0;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != F) {
					Get_Root(to[i], w);
					mx = max(sum[to[i]], mx);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(mx, area_sz - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}
		}
		
		void Build(int w, int sz) {
			vis[w] = 1;
			anc[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					area_sz = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					len[root] = len[w] + 1; 
					memcpy(anc[root]+1, anc[w], sizeof(int)*len[w]);
					Build(root, area_sz);
				}
			}
			for (int i=0;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

int main() {
	for (LL vout=0;~scanf("%d",&n);vout=T=0) {
		memset(head,0,sizeof(head));
		memset(ans,0,sizeof(ans));
		for (int i=1;i<=n;i++) 
			ori[i] = read();
		for (int i=1,u,v,w;i<n;i++) {
			u = read(); v = read(); w = read();
			Add_Edge(u, v, w);
		}	
		DFS(1, 1);
		for (int j=1;j<L;j++) { 
			for (int i=1;i<=n;i++) {
				fa[i][j] = fa[fa[i][j-1]][j-1];
			}
		}
		NDC.init(); 
		m = read();
		for (int i=1;i<=m;i++) {
			P[i] = read();
			V[i] = read();
		}
		for (int j=0;j<L;j++,vout=0) {
			memcpy(val,ori,sizeof(ori));
			NDC.prework();
			for (int i=1;i<=n;i++) {
				val[i] >>= j; val[i] &= 1;
				NDC.modify(i, val[i], 1);
				vout += NDC.query(i, val[i], j);
			}
			for (int i=1,p,v;i<=m;i++) {
				p = P[i]; v = (V[i] >> j) & 1;
				vout -= NDC.query(p, val[p], j);
				NDC.modify(p, val[p], -1);
				NDC.modify(p, v, 1);
				vout += NDC.query(p, val[p] = v, j);
				ans[i] += vout;
			}
		}
		for (int i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	} 
	return 0;
}

【CodeChef PRIMEDST】Prime Distance On Tree

相关链接

题目传送门:https://www.codechef.com/problems/PRIMEDST
官方题解:https://www.codechef.com/problems/PRIMEDST
神犇题解:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

解题报告

考虑使用点分治来统计答案,实际是求
\(\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}\)
然后发现这货是个卷积的形式,于是点分的时候搞一搞FFT就可以啦!

值得注意的是,在FFT的时候答案可能会爆int
不要问我是怎么知道的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 66000;
const int M = 110000;
const int INF = 1e9;
const double EPS = 1e-2;
const double PI = acos(-1);

int n,head[N],to[M],nxt[M];
LL vout;

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Fast_Fourier_Transform{
	typedef complex<double> E;
	complex<double> a[N<<1];
	int pri[M],vis[M],pos[N<<1],tot,len,stp;
	public:
		Fast_Fourier_Transform() {
			for (int i=2;i<M;i++) {
				if (!vis[i]) pri[++tot] = i;
				for (int j=1;j<=tot&&pri[j]*i<M;j++) {
					vis[i*pri[j]] = 1;
					if (i%pri[j] == 0) break;
				}	
			}
		}
		inline LL solve(int t, int *arr) {
			for (len=1,stp=-1;len<=t*2;len<<=1,++stp);
			memset(a,0,sizeof(E)*(len+9));
			for (int i=0;i<=t;i++) 
				a[i].real() = arr[i];
			for (int i=1;i<len;i++) { 
				pos[i] = pos[i>>1] >> 1;
				if (i & 1) pos[i] |= 1 << stp;
			} 
			
			fft(a, 1);
 			for (int i=0;i<len;i++)
				a[i] *= a[i];
			fft(a, -1);
			LL ret = 0;
			for (int i=1;i<=tot&&pri[i]<=t*2;i++)
				ret += a[pri[i]].real() / len + EPS;
			return ret;
		}
	private:
		inline void fft(E *arr, int t) {
			for (int i=0;i<len;i++)
				if (pos[i] < i) swap(arr[pos[i]], arr[i]);
			for (int k=0,gap=2;k<=stp;k++,gap<<=1) {
				E wn(cos(2*PI/gap),t*sin(2*PI/gap));
				for (int j=0;j<len;j+=gap) {
					complex<double> cur(1, 0),t1,t2;
					for (int i=j;i<j+gap/2;i++,cur*=wn) {
						t1 = arr[i]; t2 = cur * arr[i+gap/2];
						arr[i] = t1 + t2;
						arr[i+gap/2] = t1 - t2;
					}
				}
			}
		}
}FFT;

class Node_Based_Divide_and_Conquer{
	int area_size,cur_ans,root,tot;
	int sum[N],vis[N],cnt[N];
	public:
		inline void solve() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1);
			work(root, area_size);
		}
	private:
		void work(int w, int sz) {
			vis[w] = 1; 
			vout += solve(w, 0);
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					vout -= solve(to[i], 1);
					area_size = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					work(root, area_size);
				}
			}
		}
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				}
			}
			mx = max(mx, area_size - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}	
		}
		LL solve(int w, int bas) {
			memset(cnt,0,sizeof(int)*(tot+9));
			tot = 0; Get_Dis(w, bas, w);
			return FFT.solve(tot, cnt);
		} 
		void Get_Dis(int w, int d, int f) {
			cnt[d]++; 
			tot = max(tot, d);
			for (int i=head[w];i;i=nxt[i]) 
				if (to[i] != f && !vis[to[i]]) 
					Get_Dis(to[i], d+1, w);
		}
}NDC;

int main() {
	n = read();
	for (int i=1;i<n;i++) 
		Add_Edge(read(), read());
	NDC.solve();
	printf("%.10lf\n",(double)vout/n/(n-1));
	return 0;
}

【Codeforces 100633D】LWDB

相关链接

题目传送门:http://codeforces.com/problemset/gymProblem/100633/D
中文题面:http://paste.ubuntu.com/23661606/

解题报告

直接考虑将其用点分树搞
对于每一个合法的染色,我们尝试在第一个将染色点a被染色点b分开的分治点c处进行更新
因为是第一个分开的分治点,所以a、b一定在c的不同子树中
不妨设a的染色范围为d,那么对于任意点b来讲,距离c的距离 <= d-dis(a,c)就好

于是修改操作就暴力爬树高,维护一个单调栈
查询操作也是暴力爬树高,在每一个单调栈那里二分出最后生效的染色点即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int L = 20;
const int INF = 1e9;

int head[N],to[M],nxt[M],cost[M],dis[N],dep[N];
int n,m,fa[N][L];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
	fa[w][0] = f;
	dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dis[to[i]] = dis[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline int DIS(int x, int y) {
	int ret = dis[x] + dis[y];
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=L-1;~i;i--) 
		if (dep[fa[x][i]] >= dep[y]) 
			x = fa[x][i];
	if (x == y) return ret - dis[x] * 2;
	for (int i=L-1;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return ret - dis[fa[x][0]] * 2;
}

class Node_Based_Divide_and_Conquer{
	int cur_ans,root,area_size,rod[N][L];
	int sum[N],vis[N],anc[N][L],len[N];
	struct Data{
		int x,y,z;
		inline bool operator < (const Data &B) const {return x < B.x;}
		inline bool operator <= (const Data &B) const {return x <= B.x;}
	}tmp;
	vector<Data> stk[N];
	vector<Data>::reverse_iterator itr;
	public:
		inline void init() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		inline void modify(int w, int d, int c, int id) {
			tmp.y = c; tmp.z = id;
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = d - rod[w][i];
				if (tmp.x >= 0) {
					while (!stk[p].empty() && stk[p].back() <= tmp) stk[p].pop_back();
					stk[p].push_back(tmp);
				}
			}
		}
		inline int query(int w) {
			Data ret={0,0,0};
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = rod[w][i];
				itr = lower_bound(stk[p].rbegin(), stk[p].rend(), tmp);
				if (itr != stk[p].rend() && ret.z < itr->z) 
					ret = *itr;
			}
			return ret.y;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for  (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != f) {
					Get_Root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				} 
			} 
			mx = max(mx, area_size - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}
		} 
		void Build(int w, int sz) {
			vis[w] = 1; anc[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					area_size = sum[to[i]] < sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					len[root] = len[w] + 1;
					memcpy(anc[root]+1, anc[w], sizeof(anc[w])-4);
					Build(root, area_size);
				}
			}
			for (int i=1;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	DFS(1, 1); 
	for (int j=1;j<L;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	NDC.init();
	m = read();
	for (int i=1,v,d,c;i<=m;i++) {
		if (read() == 1) {
			v = read(); d = read();
			NDC.modify(v, d, read(), i);
		} else printf("%d\n",NDC.query(read()));
	}
	return 0;
}