SPOJ 913 Query on a tree II

spoj题面

Time limit 433 ms //spoj的时限都那么奇怪

Memory limit 1572864 kB //1.5个G，疯了

Code length Limit 15000 B

OS Linux

Language limit All except: ERL JS-RHINO NODEJS PERL6 VB.NET

Source Special thanks to Ivan Krasilnikov for his alternative solution

Author Thanh-Vy Hua

吐槽

期中考第二个能A的题，结果写了半个小时，调了一个半小时……纪念一下第二道被多组Case读入害死的题目……这题是把下一个case的前两个数读进来了，是这次的case没读完就进入下一个case了，这才过了两个星期啊……下次测这种样例就该把样例多复制几遍……

顺便吐槽，这是啥数据啊……一步一步地向上暴力跳都能A，亏我还跳重链……而且case之间加空行这个要求它不会判，加不加空行都是AC

解题思路

我一看见这题就没多想，直接上树链剖分，结果写完反应过来杀鸡用牛刀，这题dfs预处理一遍，倍增跳树并统计结果是更优的办法，代码可以短不少。

树链剖分处理\(KTH\)操作是利用了一个性质：一条重链上的节点新id，从上到下是连续的，所以跳链的时候如果发现跳过了目标\(k\)，那么就直接使用这条重链两端的新\(id\)计算出目标\(k\)的\(id\)，然后转换成原来的的编号即可。另外，由于这题路径有了方向，所以跳链的时候不能像平时那样std::swap(u,v)，而是要判断应该跳u还是跳v，然后分情况写。

源代码

#include
#include
#include
int T;
int n;

struct Edge{
	int nxt,to,w;
}e[200010];
int head[100010],cnt;
void add(int u,int v,int w)
{
	e[cnt]={head[u],v,w};
	head[u]=cnt++;
	e[cnt]={head[v],u,w};
	head[v]=cnt++;
}

struct Tree{
	int fa,dep,w,sz,wson;
	int top,id;
}t[100010];
void dfs1(int fa,int u,int w)
{
	t[u].fa=fa;
	t[u].dep=t[fa].dep+1;
	t[u].w=w;
	t[u].sz=1;
	int maxn=0;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs1(u,v,e[i].w);
		int temp=t[v].sz;
		t[u].sz+=temp;
		if(temp>maxn)
		{
			maxn=temp;
			t[u].wson=v;
		}
	}
}
int id=1;
int mp[100010];//用新id查询老id
long long a[100010];
void dfs2(int u,int top)
{
	t[u].top=top;
	t[u].id=id;
	a[id]=t[u].w;
	mp[id]=u;
	id++;
	if(t[u].sz==1) return;
	dfs2(t[u].wson,top);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==t[u].fa||v==t[u].wson) continue;
		dfs2(v,v);
	}
}

long long sum[400010];//线段树维护区间和
void build(int x,int l,int r)
{
	if(l==r)
	{
		sum[x]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	sum[x]=sum[x<<1]+sum[x<<1|1];
}
long long quesum(int x,int l,int r,int ql,int qr)
{
	if(qr>1;
	long long ans=0;
	if(ql<=mid) ans+=quesum(x<<1,l,mid,ql,qr);
	if(qr>mid) ans+=quesum(x<<1|1,mid+1,r,ql,qr);
	return ans;
}

long long dist(int u,int v)
{
	long long ans=0;
	while(t[u].top!=t[v].top)
	{
		if(t[t[u].top].dept[v].id) std::swap(u,v);
	ans+=quesum(1,1,n,t[u].id+1,t[v].id);
	return ans;
}

int kth(int ss,int tt,int k)//要区分起点和终点
{
	int num=0;
	int u=ss,v=tt;//先跳一遍找到总的点数
	while(t[u].top!=t[v].top)
	{
		if(t[t[u].top].dept[v].id) std::swap(u,v);
	num+=t[v].id-t[u].id+1;
	while(t[ss].top!=t[tt].top)//跳链找答案
	{
		if(t[t[ss].top].dep