meepo's Blog

    计算几何刚开始学。。然后省选讲课开始了。。。_(:з」∠)_、、、

    要同时填两个坑。。还要补我暴蛋的文化课。。。

    人生为何如此艰难。。。

    BZOJ 4016

        传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4016

       上一次写点分是九月时候。。过了这么几天模板有点忘了。。。_(:з」∠)_。。。

       回顾了一下自己写的blog发现都不会做了。。

        ——》http://wyxoi.is-programmer.com/posts/183479.html

       看了一遍blog然后码了这道题大概地熟悉了一下。。。

       这题还是比较好想的。。主要的坑点是如果直接用dijkstra求最短路树可能不符合题目的要求。。所以要先求一次最短路图求出所有在最短路上的边。。然后在图上按点的编号dfs就可以得到题目中的最短路树了。。

       然后直接点分就好了。。。

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30010;
const int M = 60010;
struct data{int x,y,s,next;} e[M<<1];
struct node{int val,id;};
struct xx{int y,s;};
struct yy{int val,sum;} f[N],g[N];
int head[N],size[N],n,m,K,ans1,ans2,cnt,vis[N],dis[N],Max[N],sum,x,y,s,deep[N],rt;
bool operator < (node a,node b){return a.val>b.val;}
priority_queue <node> heap;
vector <xx> w[N];
bool operator < (xx a,xx b){return a.y<b.y;}
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9')  x = x*10+c-'0',c = getchar();
	return x*f;
}
void Insert(int x,int y,int s){
	e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
	e[cnt].next = head[x];head[x] = cnt;
}
//**************建图****************
void dfs(int x){
	vis[x] = 1;
	for (int i=0;i<w[x].size();i++){
		int y = w[x][i].y,s = w[x][i].s;
		if (vis[y]) continue;
		if (dis[y]==dis[x]+s){Insert(x,y,s);Insert(y,x,s);dfs(y);}
	}
}
void Dijkstra(){
	for (int i=1;i<=n;i++) dis[i] = 1e9;
	dis[1] = 0;heap.push((node){0,1});
	while (!heap.empty()){
		int now = heap.top().id;heap.pop();
		//while (vis[now]) {now = heap.top().id;heap.pop();}
		if (vis[now]) continue;
		vis[now] = 1;
		for (int i=0;i<w[now].size();i++){
			int y = w[now][i].y,s = w[now][i].s;
			if (vis[y]) continue;
			if (dis[y]>dis[now]+s) {dis[y] = dis[now]+s;heap.push((node){dis[y],y});}
		}
	}
}
//**************点分*************** 
void getroot(int x,int fa){
	size[x] = 1;Max[x] = 0;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y] && e[i].y!=fa){
			getroot(e[i].y,x);
			size[x]+=size[e[i].y];
			Max[x] = max(Max[x],size[e[i].y]);
		}
	Max[x] = max(Max[x],sum-size[x]);
	if (Max[x]<Max[rt]) rt = x;
}
void dfs2(int x,int fa,int Dis){
	if (g[deep[x]].val<Dis) {g[deep[x]] = (yy){Dis,1};}
	else if (g[deep[x]].val==Dis) g[deep[x]].sum++;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y] && e[i].y!=fa){
			deep[e[i].y] = deep[x]+1;
			dfs2(e[i].y,x,Dis+e[i].s);
		}
}
void dfs3(int x,int fa){
	sum++;
	for (int i=head[x];i;i=e[i].next)
		if (e[i].y!=fa && !vis[e[i].y]) dfs3(e[i].y,x);
}
void work(int x){
	vis[x] = 1;f[0].sum = 1;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y]){
			deep[e[i].y] = 1;
			dfs2(e[i].y,x,e[i].s);
			for (int j=1;j<=K;j++){
				if (g[j].val+f[K-j].val>ans1) {ans1 = g[j].val+f[K-j].val;ans2 = 0;}
				if (g[j].val+f[K-j].val==ans1) ans2+=g[j].sum*f[K-j].sum;
			}
			for (int j=1;j<=K;j++){
				if (g[j].val>f[j].val) {f[j].val = g[j].val;f[j].sum = g[j].sum;}
				else if (g[j].val==f[j].val) {f[j].sum+=g[j].sum;}
				g[j].val = g[j].sum = 0;
			}
		}
	for (int i=0;i<=K;i++) f[i].val = f[i].sum = 0;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y]){
			sum = 0;
			dfs3(e[i].y,x);rt = 0;
			getroot(e[i].y,-1);
			work(rt);
		}
}
//********************************
int main(){
	n = read();m = read();K = read()-1;
	for (int i=1;i<=m;i++) {
		x = read();y = read();s = read();
		w[x].push_back((xx){y,s});
		w[y].push_back((xx){x,s});
	}
	for (int i=1;i<=n;i++) sort(w[i].begin(),w[i].end());
	Dijkstra();
	memset(vis,0,sizeof(vis));
	dfs(1);sum = n;rt = 0;Max[0] = 1e9;
	memset(vis,0,sizeof(vis));
	getroot(1,-1);
	work(rt);
	printf("%d %d",ans1,ans2);
}

    BZOJ 3924

    BZOJ 3730

       第一道点分树。。。写了一个星期。。。_(:з」∠)_。。。（其实是我太浪了。。）

        写完发现自己的代码能力果真和渣一样。。。调了一下午终于半死不活的调出来了。。。_(:з」∠)_。。。

        题目大意是一颗有点权的树。。求到一个点x距离小于等于K的点的权值和。。在线修改

        我们可以用点分树维护。。。在每一个点上维护一颗以到这个距离为下标的线段树。。询问的时候就一路爬父亲然后在线段树上求前缀和。。。对于重复计算的点我们可以再用一颗线段树维护后减去。。。

        修改也相似。。每次修改它祖先的线段树就好了。。。

        代码太丑了。。。就不贴了。。。

    BZOJ 1758