Category: 树

【BZOJ 1468】Tree

Qizy 24 Comments

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1468
主定理相关：http://raytaylorlin.com/Tech/algorithm/master-method/
神犇题解：http://www.cnblogs.com/iwtwiioi/p/4172279.html

题解

就是点分治的模板题啊!
另外关于主定理的话，我觉得这个式子说得很清楚：
若 $T(n) \le aT({n \over b}) + O({n^d})$
则 \(T(n) = \begin{cases} O(n^d \log n) & a = {b^d} \cr O(n^d) & a < {b^d} \cr O({n^{ { {\log }_b }a } }) & a > {b^d} \end{cases}\)

Code

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

const int N = 40000 + 9;
const int M = N << 1;
const int INF = 10000000;

int head[N],nxt[M],to[M],cost[M],vis[N],dep[N],sum[N]; 
int n,k,tot,cur,num_node,root,vout;

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 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(mx, num_node - mx);
	if (mx < cur) { 
		root = w;
		cur = mx;
	}
}

void Get_Dep(int w, int f, int bas) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f && !vis[to[i]]) {
			dep[++tot] = bas + cost[i];
			Get_Dep(to[i], w, dep[tot]);
		}
	}
}

inline int cal(int w, int bas) {
	dep[tot=1] = bas;
	Get_Dep(w, w, bas);
	sort(dep+1, dep+1+tot);
	int r = tot, l = 1, ret = 0;
	while (l < r) {
		while (l < r && dep[l] + dep[r] > k) r--;
		ret += r - l++;
	}
	return ret;
}

void solve(int w, int sz) {
	vis[w] = 1; 
	vout += cal(w, 0);
	for (int i=head[w];i;i=nxt[i]) {
		if (!vis[to[i]]) {
			vout -= cal(to[i], cost[i]);
			num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
			cur = INF; Get_Root(to[i], w);
			solve(root, num_node);
		}
	}
}

int main() {
	n = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u, v, w);
	}
	k = read();
	num_node = n; cur = INF; Get_Root(1, 1);
	solve(root, n);
	printf("%d",vout);
	return 0;
}

【BZOJ 2654】tree

Qizy 23 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2654
神犇题解：http://blog.csdn.net/PoPoQQQ/article/details/47980565

题解

感觉这个题很好玩的样子！
考虑给每一个白边加上一个固定的权值
那么使用白边的数量可以用这个权值来调整
唯一需要注意的就是，这种变化可能不是线性的
也就是说可能会有断层的情况，需要特殊处理一下

值得注意的是，这种方法具有较高的可移植性：
在某一套小火车的模拟题中，一道很恶心的DP也可以用此方法来解决

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
 
struct Edge{int u,v,val,col;}e[N]; 
int n,m,STA,fa[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;
}
 
inline int find(int w) {
    int f = fa[w], tmp;
    while (f != fa[f]) f = fa[f];
    while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
    return f;
} 
 
bool cmp_mx(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col > B.col);}
bool cmp_mn(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col < B.col);}
 
inline bool judge(int delta) {
    int cnt = 0;
    sort(e+1, e+1+m, cmp_mx);
    for (int i=1;i<=n;i++) fa[i] = i;
    for (int i=1;i<=m;i++) {
        if (find(e[i].u) != find(e[i].v)) {
            fa[find(e[i].u)] = find(e[i].v);
            cnt += e[i].col;
        }
    }
    if (cnt < STA) return 1;
     
    int cost = 0; cnt = 0;
    sort(e+1, e+1+m, cmp_mn);
    for (int i=1;i<=n;i++) fa[i] = i;
    for (int i=1;i<=m;i++) {
        if (find(e[i].u) != find(e[i].v)) {
            fa[fa[e[i].u]] = fa[e[i].v];
            cnt += e[i].col;
            cost += e[i].val; 
        }
    }
    if (cnt > STA) return 0;
    else {
        printf("%d\n",cost-STA*delta);
        exit(0);
    }
}
 
int main(){
    n = read(); m = read(); STA = read();
    for (int i=1;i<=m;i++) {
        e[i].u = read() + 1; e[i].v = read() + 1;
        e[i].val = read(); e[i].col = read() ^ 1;
    } 
     
    int l=-100,r=100,mid;
    while (l <= r) {
        mid = l + r >> 1;
        for (int i=1;i<=m;i++) if (e[i].col) e[i].val += mid;
        if (judge(mid)) r = mid - 1;
        else l = mid + 1;
        for (int i=1;i<=m;i++) if (e[i].col) e[i].val -= mid;
    } 
    return 0;
}

【BZOJ 4551】[TJOI2016&HEOI2016] 树

Qizy 2 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验：http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解：http://medalplus.com/?p=1685

题解

  1. 强制在线做法 O(nlogn)
    考虑每一次标记点：只会影响其子树中的点
    所以使用DFS序+线段树就可以辣！

  2. 离线做法 O(nlogn)
    考虑将每一次标记的时间记录到点上
    然后使用倍增LCA的思想向上倍增

  3. 离线做法 O(nα(n))
    考虑离线之后进行逆序操作
    这样的话，操作就变成了删除标记
    这个可以形象地想成：打通了向上走地道路
    于是使用并查集即可
    ps：和BZOJ_3319是一毛一样的

Code

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

const int N = 100000+9;

int head[N],to[N],nxt[N],anc[N],fa[N];
int n,m,tot,opt[N],tag[N],vout[N];
char pat[10];

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;
}

inline int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

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

void DFS(int w, int last) {
	if (tag[w]) last = fa[w] = w;
	else fa[w] = last;
	for (int i=head[w];i;i=nxt[i]) {
		anc[to[i]] = w;
		DFS(to[i],last);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u,v);
	}
	for (int i=1;i<=m;i++) {
		scanf("%s",pat+1);
		opt[i] = read(); 
		if (pat[1] == 'C') tag[opt[i]]++;
		else opt[i] *= -1;
	}
	tag[1]++; DFS(1,1);
	for (int i=m;i;i--) {
		if (opt[i] > 0) {
			if (!(--tag[opt[i]])) {
				fa[opt[i]] = anc[opt[i]];
			}
		} else {
			vout[++tot] = find(-opt[i]);
		}
	}
	while (tot) printf("%d\n",vout[tot--]); 
	return 0;
}

【BZOJ 1040】[ZJOI2008] 骑士

Qizy 101 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1040
数据生成器：http://paste.ubuntu.com/23618220/
神犇题解：http://blog.csdn.net/popoqqq/article/details/39748135

题解

看到这个题，感觉除了网络流之外别无他法
结果这货是个基环森林啊！
I well vegetable are!

这个问题搬到树上去大家都会做
原题好像叫“没有上司的舞会”？
考虑给树加上一条边之后会发生什么变化：
这条非树边要么两段的点选一个，要么都不选
于是特殊处理一下，跑三遍树上DP就可以辣！

Code

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

const int N = 1000000+9;
const int M = N << 1;

int head[N],to[M],nxt[M];
int n,val[N],aim[N],tag[N],lb,rb;
LL vout,f[N][2];

inline void Add_Edge(const int u, const int v) {
	static int T = 1;
	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 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) {
	tag[w] = 1; 
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && to[i]) {
		if (tag[to[i]]) {
			lb = w; rb = to[i];
			to[i] = to[i^1] = 0;
		} else {
			DFS(to[i], w);
		}
	}
}
 
void solve(int w, int fa) {
	f[w][0] = 0;
	f[w][1] = val[w];
	for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != fa) {
		solve(to[i], w);
		f[w][1] += f[to[i]][0];
		f[w][0] += max(f[to[i]][1],f[to[i]][0]);
	}
	if (tag[w] == 2) {
		f[w][0] = 0;
	} else if (tag[w] == 3) {
		f[w][1] = 0;
	}
}
 
int main(){
	n = read();
	for (int i=1,t;i<=n;i++) {
		val[i] = read();
		if (aim[t=read()] != i) {
			Add_Edge(i, t);
			aim[i] = t;
		}
	}
	for (int i=1;i<=n;i++) {
		if (!tag[i]) {
			LL tmp; 
			lb = rb = 0;
			DFS(i,i);
			
			tag[lb] = 2; tag = 3;
			solve(i,i);
			tmp = max(f[i][0], f[i][1]);
			
			tag[lb] = 3; tag = 2;
			solve(i,i);
			tmp = max(tmp, max(f[i][0], f[i][1]));
			
			tag[lb] = 3; tag = 3;
			solve(i,i);
			tmp = max(tmp, max(f[i][0], f[i][1]));
			vout += tmp;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 1016】[JSOI2008] 最小生成树计数

Qizy 387 Comments

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1016
优秀题解：https://blog.sengxian.com/solutions/bzoj-1016

题解

考虑最小生成树，如果使用价值相同的非树边边替换树边，得到的效果一定一样
因为不一样的话，用于替换的边就会成为最小生成树的树边
换一句话来说，权值相同的边处理完之后，图的连通性一定一样

于是暴力枚举同一权值的边的组合情况
使用并查集判断一下即可

代码

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

const int N = 100+9;
const int M = 1000+9;
const int MOD = 31011;

struct Edge{int u,v,w;}e[M];
vector<Edge> que[M];
int n,m,fa[N],fa_tmp[N],_hash[M],cnt[M],tot,vout=1,vis[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;
}

inline int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

void DFS(int w, int sz, int cur, int id, int &tmp) {
	if (cur > cnt[id]) {
		return ;
	} else if (w == sz + 1) {
		if (cur == cnt[id]) {
			memcpy(fa_tmp, fa, sizeof(fa));
			int i; for (i=1;i<=sz;i++) if (vis[i]) {
				if (find(que[id][i-1].u) == find(que[id][i-1].v)) break;
				fa[find(que[id][i-1].u)] = find(que[id][i-1].v);
			}	
			tmp += (i == sz + 1);
			memcpy(fa, fa_tmp, sizeof(fa));
		}
	} else {
		DFS(w+1, sz, cur, id, tmp);
		vis[w] = 1;
		DFS(w+1, sz, cur+1, id, tmp);
		vis[w] = 0;
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		e[i].u = u = read(); 
		e[i].v = v = read();
		_hash[i] = e[i].w = read();
	}
	sort(_hash+1, _hash+1+m);
	tot = unique(_hash+1, _hash+1+m) - _hash - 1;
	for (int i=1,tmp;i<=m;i++) {
		tmp = lower_bound(_hash+1, _hash+1+tot, e[i].w) - _hash;
		que[tmp].push_back(e[i]);
	}
	for (int i=1;i<=n;i++)
		fa[i] = i;
	for (int i=1;i<=tot;i++) {
		for (int j=que[i].size()-1;~j;j--) {
			if (find(que[i][j].u) != find(que[i][j].v)) {
				fa[find(que[i][j].u)] = find(que[i][j].v);
				cnt[i]++;
			}
		}
	} 
	for (int i=2;i<=n;i++) {
		if (find(i) != find(1)) {
			puts("0");
			exit(0);
		}
	}
	
	for (int i=1;i<=n;i++) 
		fa[i] = i;
	for (int i=1,tmp=0;i<=tot;i++,tmp=0) if (cnt[i]) {
		DFS(1,que[i].size(),0,i,tmp);
		for (int j=que[i].size()-1;~j;j--) 
			fa[find(que[i][j].u)] = find(que[i][j].v);
		(vout *= tmp) %= MOD;
	}
	printf("%d\n",vout);
	return 0;
}

【BZOJ 4326】[NOIP2015] 运输计划

Qizy 1,062 Comments

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

这货的做法就是二分之后，用DFS序判断一下
然而这货居然卡常…….
其实是↑上面这个纸张不会用指针 ╮(╯▽╰)╭
用了加强的流读入才能在UOJ上A
另外前排膜拜Menci,指针用得贼溜：https://oi.men.ci/noip2015-transport/

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

const int N = 300000+9;
const int M = N << 1;

int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(ll &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(double &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (ch=='.'){
            double tmp=1;
            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
        }
        if (bo)x=-x;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    //puts->write
    char Out[OUT_SIZE],*o=Out;
    inline void print1(int x){
        static char buf[15];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(int x){print1(x);*o++='\n';}
    inline void print1(ll x){
        static char buf[25];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(ll x){print1(x);*o++='\n';}
    inline void print1(char c){*o++=c;}
    inline void println1(char c){*o++=c;*o++='\n';}
    inline void print1(char *s){while (*s)*o++=*s++;}
    inline void println1(char *s){print1(s);*o++='\n';}
    inline void println1(){*o++='\n';}
    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
    struct puts_write{
        ~puts_write(){flush1();}
    }_puts;
    inline void print2(int x){printf("%d",x);}
    inline void println2(int x){printf("%d\n",x);}
    inline void print2(char x){printf("%c",x);}
    inline void println2(char x){printf("%c\n",x);}
    inline void print2(ll x){
        #ifdef _WIN32
            printf("%I64d",x);
        #else
        #ifdef __linux
            printf("%lld",x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void println2(ll x){print2(x);printf("\n");}
    inline void println2(){printf("\n");}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};

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; 
	in[w] = ++div_cnt;
	dep[w] = dep[f] + 1; 
	for (register int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dis[to[i]] = dis[w] + cost[i];
			sur[to[i]] = cost[i];
			DFS(to[i], w);
		} 
	}
	out[w] = div_cnt;
}

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

inline bool judge(int lim) {
	memset(delta,0,sizeof(delta));
	int cnt = 0, MN = 0, MX = 0;
	for (register int i=1;i<=m;i++) {
		if (q[i].len > lim) {
			cnt++;
			MN = max(MN, q[i].len - lim);
			delta[q[i].lca] -= 2;
			delta[q[i].u] ++;
			delta[q[i].v] ++;
		}
	}
	for (register int i=n;i;i--) 
		delta[i] += delta[i+1];
	
	for (register int i=1;i<=n;i++) {
		if (delta[in[i]] - delta[out[i]+1] >= cnt) {
			MX = max(sur[i], MX);
		}
	}
	return MX >= MN;
}

int main(){
	using namespace fastIO;
	int l=0,r=0,mid,ret;
	read(n); read(m);
	for (int i=1,u,v,w;i<n;i++) {
		read(u); read(v); read(w);
		l = max(l, w);
		Add_Edge(u, v, w);
	}
	DFS(1,1);
	for (int j=1;j<=19;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	for (int i=1,u,v,lca;i<=m;i++) {
		read(u); read(v); lca = LCA(u, v);
		q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
		r = max(r, q[i].len);
		q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
	}
	
	l = r - l; ret = r;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1; 
	}
	printf("%d\n",ret);
	return 0;
}

—– UPD 2016.11.11 —–
找高一神犇学习了一下fread的使用技巧，现在最大的一个点只用500ms辣！

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300000+9;
const int M = N << 1;
 
int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

inline char Read(){
	static const int BUF_SIZE = 1000000; 
	static char buf[BUF_SIZE],*p1=0,*p2=0;
    if (p1 == p2){
    	p1=buf; p2=buf+fread(buf,1,BUF_SIZE,stdin);
		if (p2==p1) return -1;
    } return *p1++;
} 

inline int read(){
	char c=Read(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=Read();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=Read();}
	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; 
    in[w] = ++div_cnt;
    dep[w] = dep[f] + 1; 
    for (register int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            dis[to[i]] = dis[w] + cost[i];
            sur[to[i]] = cost[i];
            DFS(to[i], w);
        } 
    }
    out[w] = div_cnt;
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (register int j=19;~j;j--) {
        if (dep[fa[u][j]] >= dep[v]) {
            u = fa[u][j];
        }
    }
    if (u == v) return v;
    for (register int j=19;~j;j--) {
        if (fa[u][j] != fa[v][j]) {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}
 
inline bool judge(int lim) {
    memset(delta,0,sizeof(delta));
    int cnt = 0, MN = 0, MX = 0;
    for (register int i=1;i<=m;i++) {
        if (q[i].len > lim) {
            cnt++;
            MN = max(MN, q[i].len - lim);
            delta[q[i].lca] -= 2;
            delta[q[i].u] ++;
            delta[q[i].v] ++;
        }
    }
    for (register int i=n;i;i--) 
        delta[i] += delta[i+1];
     
    for (register int i=1;i<=n;i++) {
        if (delta[in[i]] - delta[out[i]+1] >= cnt) {
            MX = max(sur[i], MX);
        }
    }
    return MX >= MN;
}
 
int main(){
    int l=0,r=0,mid,ret;
    n = read(); m = read();
    for (int i=1,u,v,w;i<n;i++) {
        u = read(); v = read(); w = read();
        l = max(l, w);
        Add_Edge(u, v, w);
    }
    DFS(1,1);
    for (int j=1;j<=19;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    for (int i=1,u,v,lca;i<=m;i++) {
        u = read(); v = read(); lca = LCA(u, v);
        q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
        r = max(r, q[i].len);
        q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
    }
     
    l = r - l; ret = r;
    while (l <= r) {
        mid = l + r >> 1;
        if (judge(mid)) ret = mid, r = mid - 1;
        else l = mid + 1; 
    }
    printf("%d\n",ret);
    return 0;
}

【BZOJ 3572】[Hnoi2014] 世界树

Qizy 194 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3572
数据生成器：http://paste.ubuntu.com/23376760/

一看数据范围肯定知道是虚树辣！
题解的话，让我们召唤曹清华：http://blog.csdn.net/jzhang1/article/details/50630194
然后就是恶心的码代码环节…..
人太懒，于是带了两个log，慢成翔 qwq

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int N = 300000+9;
const int M = N << 1;
const int INF = 1000000000;

int head[N],nxt[M],to[M],T,n,m,tot,num[N],blg[N],p[N],sz[N];
int stk[N],top,dep[N],fa[N][18],size[N],vis[N],vout[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;
}

inline void AddEdge(int u, int v) {to[++T] = v; nxt[T] = head[u]; head[u] = T;}
inline void Add_Edge(int u, int v) {AddEdge(u,v);AddEdge(v,u);}
inline bool CMP(int a, int b) {return num[a] < num[b];}

void DFS(int w, int f) {
	static int dfs_cnt = 0; num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f]+1; size[w] = 1;
	for (int i=1;i<=17;i++) fa[w][i] = fa[fa[w][i-1]][i-1];
	
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
			size[w] += size[to[i]];
		}
	}
}

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

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

inline void Build(int root) {
	p[++tot] = root; 
	stk[top=1] = root;
	sz[root] = n;
	
	for (int i=1,w,lca;i<=m;i++) {
		w = p[i]; lca = LCA(stk[top],w);
		while (dep[stk[top]] > dep[lca]) {
			if (dep[stk[top-1]] < dep[lca]) 
				AddEdge(lca, stk[top]);
			else 
				AddEdge(stk[top-1], stk[top]);
			top--;
		}
		if (lca != stk[top]) {
			stk[++top] = lca;
			p[++tot] = lca;
			sz[lca] = size[lca] - 1;
		} 
		if (w != stk[top]) {
			stk[++top] = w;
			sz[w] = size[w] - 1;
		}
	}
	for (int i=1;i<top;i++) 
		AddEdge(stk[i], stk[i+1]);
}

void prework_1(int w, int up) {
	blg[w] = vis[w]?w:up; 
	for (int i=head[w];i;i=nxt[i]) {
		prework_1(to[i], vis[w]?w:up);
		if (~blg[to[i]]) {
			int len1 = (~blg[w]?abs(dep[blg[w]] - dep[w]):INF);
			int len2 = abs(dep[blg[to[i]]] - dep[w]);
			if (!~blg[w] || len1 > len2 || (len1 == len2 && blg[to[i]] < blg[w])) 
				blg[w] = blg[to[i]];
		}
	}
}

void prework_2(int w) {
	for (int i=head[w];i;i=nxt[i]) {
		if (blg[w] != blg[to[i]]) {
			int len1 = dis(blg[w], to[i]);
			int len2 = dis(blg[to[i]], to[i]);
			if (len1 < len2 || (len1 == len2 && blg[w] < blg[to[i]])) 
				blg[to[i]] = blg[w];
		}
		prework_2(to[i]);
	}
}

void solve(int w) {
	for (int i=head[w],len,cur;i;i=nxt[i]) {
		top = to[i];
		for (int j=17;~j;j--) {
			if (dep[fa[top][j]] > dep[w]) 
				top = fa[top][j];
		}
		sz[w] -= size[top];
		
		if (blg[w] == blg[to[i]]) {
			vout[vis[blg[w]]] += size[top] - size[to[i]] + 1;
		} else {
			cur = to[i];
			for (int j=17;~j;j--) {
				if (dis(fa[cur][j],blg[w]) > dis(blg[to[i]], fa[cur][j])) 
					cur = fa[cur][j];
			}
			vout[vis[blg[to[i]]]] += size[cur] - size[to[i]] + 1;
			if (dep[fa[cur][0]] > dep[w] && dis(fa[cur][0], blg[w]) == dis(fa[cur][0], blg[to[i]])){
				vout[vis[min(blg[w], blg[to[i]])]] += size[fa[cur][0]] - size[cur];
				vout[vis[blg[w]]] += size[top] - size[fa[cur][0]];
			} else {
				vout[vis[blg[w]]] += size[top] - size[cur];
			}
		}
		solve(to[i]);
	}
	vout[vis[blg[w]]] += sz[w];
}

int main(){
	n = read();
	for (int i=1;i<n;i++) 
		Add_Edge(read(),read()); 
	DFS(1,1);
	
	T = 0; memset(head,0,sizeof(head));
	for (int q=read(),lca;q;q--) {
		m = tot = read(); 
		lca = p[1] = read();
		vis[p[1]] = 1; vout[1] = 0;
		for (int i=2;i<=m;i++) {
			vis[p[i]=read()] = i;
			lca = LCA(lca, p[i]);
			vout[i] = 0;
		}
		sort(p+1, p+1+m, CMP);
		
		Build(lca);
		prework_1(lca,-1);
		prework_2(lca);
		solve(lca);
		for (int i=1;i<=m;i++) {
			printf("%d ",vout[i]);
		} putchar('\n');
		
		for (int i=1;i<=tot;i++) {
			vis[p[i]] = head[p[i]] = 0;
		} T = 0;
	}
	return 0;
}

【BZOJ 2286】[Sdoi2011] 消耗战

Qizy 22 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2286
数据生成器：http://paste.ubuntu.com/23372796/

就是把虚树建出来了以后，在虚树上跑树上DP
DP很好想，只需要会建虚树就可以辣！

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

const int SGZ = 18;
const int M = 500000+9;
const int N = 250000+9;
const int INF = 0x7fffffff;

int head[N],nxt[M],to[M],cost[M],dep[N],fa[N][SGZ],MN[N][SGZ];
int n,m,p[N],num[N],stk[N],top,tot,T;
bool vis[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;
}

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

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;
}

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

inline bool CMP(const int &x, const int &y) {
	return num[x] < num[y];
}

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

inline int Get_Cost(int w, int pur) {
	int ret = INF; pur = dep[pur];
	for (int i=17;~i;i--) {
		if (dep[fa[w][i]] >= pur) {
			ret = min(ret, MN[w][i]);
			w = fa[w][i];
		}
	}
	return ret;
}

inline void build() {
	stk[top = 1] = 1;
	for (int i=1,w,lca;i<=m;i++) {
		w = p[i]; lca = LCA(stk[top], w);
		while (dep[stk[top]] > dep[lca]) {
			if (dep[stk[top-1]] <= dep[lca]) 
				Add_Edge(lca, stk[top]);
			else 
				Add_Edge(stk[top-1], stk[top]);
			--top;
		}
		if (stk[top] != lca) stk[++top] = lca, p[++tot] = lca;
		stk[++top] = w;
	}
	for (int i=1;i<top;i++) 
		Add_Edge(stk[i], stk[i+1]);
}

inline LL DP(int w, int f) {
	LL tmp = 0;
	for (int i=head[w];i;i=nxt[i]) 
		tmp += DP(to[i], w);
	if (vis[w]) return Get_Cost(w, f);
	else if (w != 1) return min((LL)Get_Cost(w, f), tmp);
	else return tmp;
}

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); MN[1][0] = INF;
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
			MN[i][j] = min(MN[i][j-1], MN[fa[i][j-1]][j-1]);
		}
	} 
	
	memset(head,0,sizeof(head));
	for (int k=read();k;k--) { 
		m = tot = read(); T = 0; 
		for (int i=1;i<=m;i++) vis[p[i] = read()] = 1;
		sort(p+1, p+1+m, CMP);
		build();
		printf("%lld\n",DP(1,1)); head[1] = 0;
		for (int i=1;i<=tot;i++) vis[p[i]] = 0, head[p[i]] = 0;
	}
	return 0;
}

【51NOD 1806】wangyurzee的树

Qizy 75 Comments

题目传送门：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1806
数据生成器：http://paste.ubuntu.com/23358513/

这题知道Prufer编码的同学都能一眼秒吧？
就是裸的Prufer加上容斥。
但这题细节比较多，我说说我被坑的两个地方吧：
1）可能有多个限制条件针对一个点，在容斥的时候要排除这种情况
2）容斥的时候，所有点的度都确定了，但度数不等于n-2的情况容斥也要排除掉

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

const int M = 20;
const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;

int POW[N],REV[N],lim[M],id[M],n,m,vout,vis[N];
set<pair<int,int> > S;

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;
}

inline int pow(int w, int t) {
	if (!w || t <= 0) return 1; int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	} return ret;
}

inline int C(int x, int y) {
	int ret = (LL)POW[y] * REV[x] % MOD;
	return (LL)ret * REV[y-x] % MOD;
}

void DFS(int t, int tot, int cnt, int sol, int f) {
	if (tot < 0 || (tot > 0 && cnt == n)) return;
	else if (t >= m + 1) {
		if (!cnt) return;
		else {
			sol = (LL)sol * pow(n - cnt,tot) % MOD;
			vout = ((vout + f*sol) % MOD + MOD) % MOD; 
		}
	} else {
		DFS(t+1, tot, cnt, sol, f);
		if (!vis[id[t]]) {
			vis[id[t]] = 1;
			DFS(t+1, tot - lim[t], cnt + 1, (LL)sol * C(lim[t],tot) % MOD, -f);
			vis[id[t]] = 0;
		}
	} 
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		id[i] = read(), lim[i] = read() - 1;
		if (S.count(make_pair(id[i],lim[i]))) {
			i--; m--;
		} else {
			S.insert(make_pair(id[i],lim[i]));
		}
	}
	POW[1] = REV[1] = POW[0] = REV[0] = 1;
	for (int i=2;i<=MX;i++) POW[i] = (LL)POW[i-1] * i % MOD;
	REV[MX] = pow(POW[MX], MOD - 2);
	for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1] * (i + 1) % MOD;
	
	vout = pow(n, n-2);
	DFS(1,n-2,0,1,1);
	printf("%d\n",vout);
	return 0;
}

【BZOJ 1086】[SCOI2005] 王室联邦

Qizy 2 Comments

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

来学习树上莫队的前置技能——树分块
题解让我们来%Po娘：《手把手教你块状树系列》

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

const int N = 1000+9;
const int M = N * 2;

int head[N],to[M],nxt[M],stk[M],top;
int num[N],pri[N],n,lim,cnt; 

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;
}

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;
}

void DFS(int w, int f, int bot) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i],w,top);
			if (top - bot >= lim) {
				pri[++cnt] = w;
				for (int i=top;i>bot;i--) {
					num[stk[i]] = cnt;
				}
				top = bot;
			}
		}
	}
	stk[++top] = w;
}

int main(){
	n = read(); lim = read();
	for (int i=1;i<n;i++) {
		Add_Edge(read(),read());
	}
	
	DFS(1,1,0);
	while (top) {
		num[stk[top--]] = cnt;
	}
	
	printf("%d\n",cnt);
	for (int i=1;i<=n;i++) {
		printf("%d%c",num[i],i==n?'\n':' ');
	}
	for (int i=1;i<=cnt;i++) {
		printf("%d ",pri[i]);
	}
	return 0;
}

【BZOJ 1005】[HNOI2008] 明明的烦恼

Qizy 195 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1005
数据生成器：http://paste.ubuntu.com/23338303/

这题和BZOJ_1211几乎一毛一样
唯一的区别：这题要写高精 qwq
于是果断弃疗，扔一份不带高精的代码：

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

const int N = 1000+9;
const int MX = 1000;

int C[N][N],res,n,emp;
LL vout=1; 

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;
}

inline void prework(){
	C[0][0] = C[1][1] = C[0][1] = 1;
	for (int j=1;j<=MX;j++) {
		C[0][j] = 1;
		for (int i=1;i<=j;i++) {
			C[i][j] = C[i][j-1] + C[i-1][j-1];
		}
	}
}

int main(){
	if ((n=read()) == 1) {
		if (!read()) puts("1");
		else puts("1");
	} else if (n == 2) {
		if (read() == 1 && read() == 1) puts("1");
		else puts("0");
	} else {
		prework(); emp = n - 2;
		for (int i=1,tmp;i<=n;i++) {
			if ((tmp=read()) == -1) {
				res++;
			} else {
				vout *= C[tmp-1][emp];
				emp -= tmp - 1;
			}
		}
		if (emp < 0) puts("0");
		else {
			for (int i=1;i<=emp;i++) {
				vout *= res;
			}
			cout<<vout;
		}
	}
	return 0;
}

【BZOJ 1211】[HNOI2004] 树的计数

Qizy 2 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1211
数据生成器：http://paste.ubuntu.com/23338142/

这题知道prufer编码的人做起来是大水题吧？
可以搞一搞组合数，或者直接上可重集的全排列？

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

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;
}

inline int C(const int &a, const int &b) {
	static int ret; ret = 1;
	for (int i=1;i<=b;i++) ret *= i;
	for (int i=1;i<=a;i++) ret /= i;
	for (int i=1;i<=b-a;i++) ret /= i;
	return ret;
}

int main(){
	int n=read();
	if (n == 1) {
		if (read() == 0) puts("1");
		else puts("0"); 
	} else if (n == 2) {
		if (read() == 1 && read() == 1) puts("1");
		else puts("0");
	} else {
		n -= 2; LL vout = 1;
		for (int i=n+2,tmp;i;i--) {
			vout *= C(tmp=read()-1,n);
			n -= tmp;
		}
		if (n == 0) cout<<vout;
		else puts("0");
	}
	return 0;
}

【BZOJ 1430】小猴打架

Qizy 2 Comments

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

首先，根据Cayley公式可以得到prufer序列和生成树一一对应
于是生成树的个数就有n^(n-2)个
另外，他求的还是排列数，所以还要乘上(n-1)条边的排列

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

const int MOD = 9999991;

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;
}

int main(){
	int n = read(), vout = 1;
	for (int i=1;i<=n-2;i++) {
		vout = (LL)vout * n % MOD;
	}
	for (int i=n-1;i;i--) {
		vout = (LL)vout * i % MOD;
	}
	cout<<vout<<endl;
	return 0;
}

【BZOJ 2851】极限满月

Qizy 21 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2851
数据生成器：http://paste.ubuntu.com/23321973/

这道题我真的是服了。 服气！
0_7uftv1i06u7jhr9

如果考虑{ai}为父亲集合的话
这货是个DAG
然后看一看{bi}中涉及到的∩操作
从顶端向下考虑的话，这™不就是支配点！
于是求一求灾难树，然后求一求路径并

话说这么巧妙的题目出题人是怎么想到的！
服！ 真心服！

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

const int N = 200000+9;
const int M = N*200;

int head[N],nxt[M],to[M],n,m,in[N],out[N];
int que[N],fa[N][18],dep[N],num_cnt;
vector<int> G[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;
}

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

inline bool cmp(const int &a, const int &b) {
	return in[a] < in[b];
}

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

inline void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (!~fa[to[i]][0]) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0], w);
		}
		
		if (!--in[to[i]]) solve(to[i]);
	}
}

void DFS(int w) {
	in[w] = ++num_cnt;
	for (int i=G[w].size()-1;~i;i--) {
		DFS(G[w][i]);
	}
	out[w] = num_cnt;
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j--) {
			Add_Edge(read(),i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	DFS(0);
	
	m = read(); 
	for (int k=1,len,vout=0;k<=m;k++,vout=0) {
		len = read();
		for (int j=1;j<=len;j++) {
			que[j] = read();
		}
		
		sort(que+1,que+1+len,cmp);
		for (int i=1,pre=0;i<=len;i++) {
			vout += dep[que[i]];
			vout -= dep[lca(pre,que[i])];
			pre = que[i];
		}
		
		printf("%d\n",vout);
	}
	return 0;
}

—– UPD 2016.10.16 —–
今天发现这题数据范围有问题
关系数应该是小于2e6
点数应该是小于2e5

【BZOJ 2815】[ZJOI2012] 灾难

Qizy 217 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2815
题面传送门：http://blog.csdn.net/flaze_/article/details/51334708

这题好好玩！
让我们来膜拜fanhq666:
http://fanhq666.blog.163.com/blog/static/8194342620124274154996/

这题把数学模型抽象出来就是：
给一个有向无环图，问每个节点删掉之后会导致多少个点不可达。
感觉还是挺有用的样子!

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

const int N = 100000;
const int M = 1000000;

int head[N],to[M],nxt[M],fa[N][18];
int in[N],sz[N],dep[N],n; 
vector<int> G[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;
}

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

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

void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (fa[to[i]][0] == -1) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0],w);
		}
		
		if (--in[to[i]] == 0) {
			solve(to[i]);
		}
	}
}

void Get_Size(int w) {
	sz[w] = 1;
	for (int i=G[w].size()-1;~i;i--) {
		Get_Size(G[w][i]);
		sz[w] += sz[G[w][i]];
	}
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j=read()) {
			Add_Edge(j,i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	Get_Size(0);
	
	for (int i=1;i<=n;i++) {
		printf("%d\n",sz[i] - 1);
	}
	return 0;
}

【BZOJ 3569】DZY Loves Chinese II

Qizy 88 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器：http://paste.ubuntu.com/23227745/

这个题，是我到目前为止，做过的最妙的一道题
没有之一

给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况：删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样，判一下是否线性无关即可

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

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971; 
const int SGZ = 40;

int head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[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;
}

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

void DFS1(int w, int f) {
	vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (vis[to[i]]) {
			int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
			sym[w] ^= W; sym[to[i]] ^= W;	
		} else DFS1(to[i],w);
	}
}

void DFS2(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i]) 
		DFS2(to[i], w), val[i] ^= sym[to[i]], 
		val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
	for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
		if (!bas[i]) {bas[i] = tmp; return false;}
		else {tmp ^= bas[i]; if (!tmp) return true;}
	} return val[w]?false:true;
}

int main(){
	srand(9999971); n = read(); m = read(); 
	for (int i=1;i<=m;i++) Add_Edge(read(),read());
	DFS1(1,1); DFS2(1,1);
	for (int q=read(),k,tag;q;q--) {
		k = read(); tag = 1; memset(bas,0,sizeof(bas));
		for (int i=1;i<=k;i++) c[i] = read()^cnt;
		for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
		if (tag) puts("Connected"), cnt++;
	}
	return 0;
}